[백준] Swift - 1931번: 회의실 배정

👆문제풀러 가기👆

문제

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

입력

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

출력

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

알고리즘 분류

• 그리디 알고리즘
• 정렬

---

풀이 [메모리: 76812KB,  시간: 168ms]

let n = Int(readLine()!)!
var timeArr = [[Int]]()
var result = 0

// 회의 시작, 종료 시간을 timeArr에 저장
for _ in 0..<n {
    let time = readLine()!.split(separator: " ").map { Int($0)! }
    timeArr.append(time)
}

// timeArr를 시작, 종료 시간을 기준으로 오름차순 정렬
timeArr.sort { (a: [Int], b: [Int]) -> Bool in
    if a[1] == b[1] {
        return a[0] < b[0]
    } else {
        return a[1] < b[1]
    }
}

var temp = 0

for i in 0..<timeArr.count {
    // 현재회의 종료시간 <= 다음회의 시작시간 
    if temp <= timeArr[i][0] {
    	// 회의 횟수 카운트
        result += 1
        // 다음회의 종료시간을 비교를 위해 저장
        temp = timeArr[i][1]
    }
}
print(result)

 

백준 '단계별 문제'의 '그리디 알고리즘' 중 2차원 배열의 정렬이 익숙지 않았던 내겐 가장 까다롭다고 느꼈던 문제.