[백준]1931_회의실 배정

문항번호: 1931번 회의실 배정

tags: problem solving

1. 문제 분석

목표: 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수 찾기

2. 풀이 계획

• 입력 제한 : N(1 ≤ N ≤ 100,000)
• 시간 제한 : 2초

생각한 방향

• 최대한 회의를 많이 하기 위해서는 가급적 빠른 시간에 끝나는 회의를 선택하는 방법을 선택해야한다.

1. 빠른 시간에 끝나는 회의임을 찾기 위한 정렬 과정이 요구된다. -> sort() 메서드 사용
2. 추가로 다음에 시작할 수 있는 회의는 현재의 종료시간 이후이거나 같은 값을 가져야 한다. -> if 조건문

3. 계획 검증

• 시간 복잡도 예상 : 최대 100,000개의 데이터가 들어온다고 가정했을 때, Swift에서 제공하는 sort 함수의 시간복잡도는 O(NlogN)이고, For문 하나를 활용했을 때 시간 복잡도는 O(n)이므로 풀이 계획대로 풀면 정답값을 추론해낼 수 있을 것 같다.

4. 소스 코드

import Foundation

let N = Int(readLine()!)!

var meetings = [(start: Int, end: Int)]()

for _ in 0..<N {
    let meeting = readLine()!.split(separator: " ").map { Int(String($0))!}
    meetings.append((start: meeting[0], end: meeting[1]))
}

let waiting = meetings
    .sorted { $0.start < $1.start }
    .sorted { $0.end < $1.end }   

var result = 0
var end = 0
for value in waiting {
    if value.start >= end {
        result += 1
        end = value.end
    }
}

print(result)

5. 돌아 보기

사용된 알고리즘

• 정렬 알고리즘
• 그리디 알고리즘

여러 종류가 있지만, 그리디 알고리즘 문항의 경우, 현재의 상황에서 최선의 선택을 하게 될 경우, 최적 선택이 이뤄지도록 문항이 구성되는 듯 하다.
추가로 위 문항에서는 튜플과 같은 사용자 자료형의 정렬을 요구했다.
사용자 정의 자료형의 정렬이나 비교에 대해서 추가적인 공부를 하는게 좋겠다.