[Swift Algorithm] 회의실 배정 BOJ #1931

문제 설명

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

 

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

 

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

 

입출력 예제

입력

11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

출력

4

 

내 문제 풀이

import Foundation

let count = Int(readLine()!)! // 회의 총 개수
var times = [[Int]]() // 회의 시작, 끝 시간 저장하는 2차원 배열
var answer = 0

for _ in 0..<count  {
    let input = readLine()!.split(separator: " ").map({Int(String($0))!})
    times.append([input[0], input[1]])
}

times.sort(by: { $0[0] < $1[0] }) // 시작하는 시간 기준 오름차순 정렬
times.sort(by: { $0[1] < $1[1] }) // 끝나는 시간 기준 오름차순 정렬

var check = 0

for i in times {
    if i[0] >= check {
        check = i[1]
        answer += 1
    }
}

print(answer)

👉 시작하는 시간, 끝나는 시간이 쌍으로 하나의 요소를 이루는 2차원 배열을
시작하는 시간을 기준으로 오름차순 정렬한 뒤, 다시 끝나는 시간을 기준으로 오름차순 정렬한다는 점이 포인트!

• 시작하는 시간과 끝나는 시간을 차례대로 times 2차원 배열에 저장했다.
• 그리고 time 배열을 시작 시간 기준 오름차순 정렬 후, 끝 시간 기준 오름차순 정렬했다.
  이렇게 한 이유는, 같은 시작 시간일 경우 끝나는 시간이 빠를수록 효율적인 회의 배정이 가능하기 때문이다.
• 위와 같이 정렬한 후, time 배열을 순서대로 검색하며 효율적인 회의들을 찾을 때마다 answer에 +1 해주었다.
  for문을 자세히 설명하면, 예를 들어 [2, 3], [2, 5], [3, 6] 이렇게 회의가 있을 경우
  [2, 3] 회의의 끝나는 시간인 3으로 check 변수를 갱신해주고,
  그 다음엔 check, 즉 3부터 시작하는 회의가 있는지 검색해준다.
  [2, 5]는 2가 3보다 작으므로 그냥 넘어가고, [3, 6] 회의가 if 조건에 해당된다.

 

💡 피드백

• 그리디 문제들은 대체적으로 정렬을 잘 활용해야 하는 문제가 많은 것 같다.
• 처음 이 문제를 풀었을 때는 한 배열을 각각의 요소를 기준으로 두 번 정렬한다는 방법이
  생각나지 않아 시간초과됐었는데, 이런 방법도 있다는 것을,, 깨달으니 문제가 너무 간결히 풀렸다.

 

---

 

문제

https://www.acmicpc.net/problem/1931