[Swift] BOJ 1931회의실 배정

BOJ 1931회의실 배정

 

 

✅ 알고리즘 자체는 쉬웠음

먼저 정렬을 해야하는데, 끝나는 시간을 기준으로 수행하며 만약 그 끝나는 시간이 같다면 시작 시간이 빠른 것을 앞에다가 배치함.

그 이후로는 그리디(그냥 for문 다 돌리라는 말)로 풀면 되는데, 현재 시간과 시작시간을 비교해서 시작시간이 같거다 더 뒤에 있으면 카운트를 증가시키고 현재 시간을 끝나는 시간으로 바꿔주면 된다.

 

포스팅을 한다는 건 생각보다 오래 걸렸단 말이겠지?

백준 문제가 너무 불친절해서,, 테스트 케이스가 하나만 있던데, 당연히 정렬이 되어있는줄 알았음.

정렬이 안되어 있어서 그래서 정렬하니까 완료

 

나는 처음에 85%쯤에서 막혔는데 반례를 찾았음

 

[반례]

3

3 3

2 3

3 3

 

올바른 답: 3

 

let iterator : Int! = Int(readLine()!)! // 1..<100000 정수
        
        var time_list: [(Int, Int)] = []
        for _ in 0..<iterator {
            let input = readLine()!.split(separator: " ")
            let start: Int = Int(input[0])!
            let end: Int = Int(input[1])!
            time_list.append((start, end))
        }
        
        // 정렬
        time_list = time_list.sorted {
            if $0.1 == $1.1 {
                return $0.0 < $1.0
            }
            return $0.1 < $1.1
        }
        
        // 알고리즘 구현
//        print(time_list)
        var currentTime = 0
        var count = 0
        time_list.forEach { start, end in
            if start >= currentTime { // 회의 가능한 케이스
//                print("-> \(start) \(end)")
                count += 1
                currentTime = end
            }
        }
        print(count)