[Swift] 백준, 회의실 배정

문제 링크

백준, 회의실 배정

잡담

오늘 마지막으로 푼 문제입니다.. 이번엔 테스트 케이스는 다 통과 되었지만, 시간 초과 ㅎㅎㅎㅎㅎㅎ 🤯

하.. 어렵다어려워.. 그래도 정답률이 20%라서 저만 잘 못푼게 아니니까 너무 좌절은 안할려구요!

풀이 가시죠!

풀이

저는 처음에 시작시간을 기준으로 정렬하고, 배열에서 첫 번째부터 하나씩 빼주면서 끝난 시간을 바꿔주면서 다음으로 넘어갔습니다.

그런 다음, 모든 강의들을 시작 시점으로 생각했을 때를 계산해줬었는데요.. 이러면 완전탐색이네요 ㅋㅋㅋ 이건 그리디였는데.. 그래서 시간초과가 났던 것 같아요 ㅎㅎ

자! 잘 생각해보면 끝나는 시간이 가장 빠른거부터 쭉쭉가다보면 결국 가장 많은 강의를 넣을 수 있더라구요.. 생각보다 공식은 간단했습니다.

사실상 시작 시간은 상관없었던 부분이죠 ㅋㅋㅋ 아! 비교할 때 이전 강의의 끝나는 시간과 다음 강의의 시작시간을 비교해야 되긴하네요. 그런데 정렬할 땐 필요없습니다.

결국 순서는,

• 입력받은 값들을 끝나는 시간을 기준으로 오름차순 정렬한다.
• 정렬 후, 배열을 순차적으로 순회하면서 끝난 시각과 다음 강의의 시작시간과 비교한다.
• 시작 시간이 더 크거나 같을 경우, 끝난 시각을 다음 강의의 끝난 시간으로 변경해주고 count를 1 증가시킨다.

입니다.

코드

//
//  main.swift
//  회의실배정
//
//  Created by 남기범 on 2020/12/30.
//  Copyright © 2020 남기범. All rights reserved.
//

import Foundation

let string = readLine()!
let length = Int(string)!
var arr = [(end: Int, start: Int)]()
var result = 0

for _ in 0..<length {
    let line = readLine()!.components(separatedBy: " ").map { Int($0)! }
    arr.append((line[1], line[0]))
}

arr.sort(by: <)

var now = 0
for element in arr where element.start >= now {
    now = element.end
    result += 1
}

print(result)