BOJ_1931_회의실 배정 [그리디 알고리즘]

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

이 문제는 두 가지로 나누어 서술하겠습니다.

 

1. 풀이 방법

2. 튜플의 사전식 순서를 이용한 stable sort

swift 에서 튜플을 이용했을 때 ‘사전식 순서’ 를 이용한 stable sort 방법을 사용하는 방법이 있어서

신기해서 정리해보았습니다.

1. 풀이 방법 - 정렬기준을 정하는 방법

그리디 알고리즘답게 눈에 보이는 것을 먼저 파악해본다면,

일단 빨리 시작하고 빨리 끝나야 가장 많은 회의를 할 수 있겠구나! 라는 생각이 든다.

그렇다면 두 가지의 정렬기준이 생겼다.

• 회의가 빨리 시작하는 것을 우선으로 한다.
• 회의가 빨리 끝나는 것을 우선으로 한다.

이 두가지를 결합하면 되는데 어떤 것을 먼저 정렬해야할지 고민이 생긴다.

이 부분은 뭐가 더 우선순위인지 생각해보자

이 문제를 해결하는데 있어서 가장 중요한 점은 “최대한 많은 회의를 진행해야 한다” 라는 점이다.

첫 회의를 생각 했을 때, 가장 빠른 시간에 끝나는 것을 시작으로

첫 회의가 끝나는 시간 이 후 → 다음 회의가 시작하는 가장 빠른 시간

다음 회의가 끝나는 시간 이후 → 그 다음 회의가 시작하는 가장 빠른 시간

이러한 형식으로 진행되기에

하나의 회의가 끝나는 시간과 다음 회의가 시작하는 시간이 겹치지 않게 스케줄을 짜야 하고,

이를 위해선 "회의가 빨리 끝나는 순서"를 먼저 고려하는 것이 효율적이다.

그럼, 모든 회의를 봤을 때 회의가 끝나는 시간끼리 비교했을 때

끝나는 시간이 다르다면 끝나는 시간을 기준으로 오름차순으로 정렬

끝나는 시간이 같다면 시작 시간을 기준으로 오름차순 정렬을 하게 된다.

이렇게 정렬한 후에는 회의 시간을 순회하며,

최근에 끝난 회의의 시간이 다음 회의의 시작 시간보다 작거나 같은 경우에만 회의를 진행하면 된다.

이 때, 겹치는 회의 시간을 걸러낼 수 있다.

본인이 작성한 코드

struct meeting {
    let start: Int
    let end: Int
}

let N = Int(readLine()!)!
var list: [meeting] = []
var count = 0
var recentMettingEndTime = 0
for _ in 0..<N {
    let input = readLine()!.split(separator: " ").map { Int($0)! }
    let data: meeting = meeting(start: input[0], end: input[1])
    list.append(data)
}

// 일단 빨리 시작하고 빨리 끝나는게 좋으니 그걸 기준으로 정렬
// 회의가 끝나는 시간이 다른지 확인
// 다르다면, 빨리 끝나는 순서대로 오름차순 정렬
// 같다면, 회의가 빨리 시작하는 순서대로 오름차순 정렬
list.sort { $0.end != $1.end ? $0.end < $1.end : $0.start < $1.start }

for i in 0..<list.count {
    // 최근에 끝난 회의시간이 list[i] 의 시작시간보다 작거나 같은지 확인 (이 과정중에 겹치는 회의시간을 걸러낼 수 있음)
    if recentMettingEndTime <= list[i].start {
        // 최근에 끝난 회의시간을 이번 요소의 끝난시간으로 넣어주고, count += 1
        recentMettingEndTime = list[i].end
        count += 1
    }
}

print(count)

 

---

2. 튜플의 사전식 순서를 이용한 stable sort

튜플을 이용한 다른 풀이 코드를 먼저 올리면서 설명하겠습니다.

let N = Int(readLine()!)!
var meetingList = [(end: Int, start: Int)]()

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

meetingList.sort { $0 < $1 }

var recentMeetingEndTime = meetingList[0].end
var count = 1

for index in 1..<N {
    if recentMeetingEndTime <= meetingList[index].start {
        count += 1
        recentMeetingEndTime = meetingList[index].end
    }
}

print(count)

코드를 보면 meetingList 에 처음으로 들어온 요소는 end, 그 다음으로 들어온 요소는 start 이다.

그러고 meetingList { $0 < $1 } 만 해버렸는데 $0.end < $1.end 이런것도 아니고

그냥 깡으로 작성했는데도 정렬이 되는 점이 신기해서 찾아봤더니 사전식 순서라는 방식이 존재했다.

Swift에서는 기본적으로 튜플에 대한 비교 연산을 제공하며,

이는 튜플의 첫 번째 요소부터 시작해서 순차적으로 비교한다.

swift는 현재 컴파일시점에서 meetingList { $0 < $1 }는 튜플의 내부 구조를 알고 있다.

즉, $0 < $1는 먼저 튜플의 end 값을 비교하고, 만약 end 값이 같다면 start 값을 비교하게 된다.

이는 튜플의 첫 번째 요소인 end로 오름차순 정렬한 후,

그 안에서 두 번째 요소인 start로 다시 정렬하는 것과 같고,

이러한 비교 방식을 '사전식 순서'라고 한다.

그렇다면 여기서 의문점이 발생했다.

그럼 정렬되는 순서가

1. 회의가 끝나는 시간 오름차순 정렬이 완료된 배열을 뱉어내고
2. 뱉어낸 배열을 이용해서 다시 회의가 시작하는 시간 순으로 재정렬해서 새로운 배열을 뱉어내는 건가?

하지만, 이것은 아니었다.

Swift의 튜플 비교는 사전식 순서를 따르는데,

이는 두 번의 별도의 정렬 과정을 거치는 것이 아니라 한 번의 정렬 과정에서 두 요소를 모두 고려한다.

즉, 튜플 (end, start)에 대해 정렬을 수행하면 다음과 같은 순서로 비교가 이루어진다.

1. 첫 번째 요소인 end를 비교 → end 값이 다르다면, 이를 기준으로 정렬이 이루어지고, 이 시점에서 이미 정렬이 완료된 상태
2. 만약 end 값이 같다면, 두 번째 요소인 start를 비교 → 이 값이 다르다면, 이를 기준으로 정렬이 이루어짐

따라서 한 번의 정렬 과정에서 end와 start를 모두 고려하여 정렬이 이루어지는 것이다.

이는 단순히 end로 정렬한 후 start로 다시 정렬하는 것과는 다른 개념으로

사전식 순서는 첫 번째 요소부터 비교를 시작해서, 같은 값이 나오는 경우에 한해 그 다음 요소를 비교하는 방식으로 동작한다.

그럼 이제 또 의문점이 발생한다.

1. end 같은 경우에는 같으면 다음 튜플 요소로 가서 또 비교할 수 있었다.
2. start 의 입장에서는 같을경우 다음 튜플 요소로 갈 수가 없어서 비교하는 대상이 없는데 이때는 오류가 나야하는 것이 아닌가?

하지만, 놀랍게도 start 값이 같은 경우에도 오류가 발생하지 않는다.

Swift 의 튜플 비교는 각 튜플 요소를 순차적으로 비교하는데,

만약 모든 요소를 비교한 결과 두 튜플이 동일하다면 그 두 튜플은 정렬 과정에서 서로의 위치를 바꾸지 않는다.

즉, '안정적인(stable)' 정렬이라고 할 수 있다.

예를 들어, 두 튜플 (end1, start1)과 (end2, start2)를 비교하면,

먼저 end1과 end2를 비교한다.

만약 end1 == end2라면, 그다음 요소인 start1과 start2를 비교한다.

여기서 start1 == start2라면, 두 튜플은 동일하다고 판단하고 정렬 과정에서 그들의 위치를 바꾸지 않는다.

따라서 start 값이 같은 경우에도 다음 튜플 요소로 이동할 필요가 없으므로, 오류가 발생하지 않는 것이었다.