[백준] (Swift) 1931번 - 회의실 배정 (실버1) (feat. 그리디, 탐욕법)

🟠 문제 링크

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

1931번: 회의실 배정

 

🟠 나의 풀이

아이패드로 그림을 그리면서 생각해보니, 주어진 입력값을 잘 정렬한다면, 순서대로 더해가면서 정답을 찾을 수 있을 것 같았다.

우선 많은 회의를 하기 위해서는, 동일한 시간에 시작하는 회의는 최대한 빨리끝나야한다. 이유는 빨리 끝날수록 뒤에서 고려해볼 회의가 많기 때문이다.

그래서 시작시간을 순서로 먼저 정렬해준뒤, 종료시간을 기준으로 다시 한 번 정렬시켜주어야 한다. 

정렬된 후에 prevEndTime이라는 변수에 끝나는 시간을 넣어주고, 각 회의마다 start 시간을 비교해준다. 시작시간이 prevEndTime보다 크거나 같으면 cnt 를 1 증가시켜주고, prevEndTime을 바꿔준다.

 

🟠 정답 코드

https://github.com/deslog/Algorithm/blob/main/Algorithm/Boj/1931_%ED%9A%8C%EC%9D%98%EC%8B%A4%20%EB%B0%B0%EC%A0%95/main.swift

GitHub - deslog/Algorithm

import Foundation

// input
let n = Int(readLine()!)!
var meeting = [[Int]]()
for _ in 0..<n {
    let temp = readLine()!.split(separator: " ").map { Int(String($0))! }
    meeting.append(temp)
}

// main
func solution(_ meeting: [[Int]]) -> Int {
    // meeting 오름차순으로 정렬
    var sortedMeetings = meeting
    sortedMeetings.sort{ return $0[0] < $1[0] }
    sortedMeetings.sort{ return $0[1] < $1[1] }

    var cnt = 0
    var prevEndTime = 0

    for meeting in sortedMeetings {
        let start = meeting[0]
        let end = meeting[1]

        if start >= prevEndTime {
            cnt += 1
            prevEndTime = end
        }
    }
    return cnt
}

print(solution(meeting))