Baekjoon #1931 - 회의실 배정

목차

1. 문제

2. 입출력 예시

3. 문제 풀이

1. 문제

• 백준알고리즘 문제 - 1931번 회의실 배정

2. 입출력 예시

입력 예시	출력 예시
11 1 4 3 5 0 6 5 7 3 8 5 9 6 10 8 11 8 12 2 13 12 14	4

3. 문제 풀이

이 문제는 생각보다 까다로운 문제였다. 가정사항을 세운 후 수 차례 가정사항을 수정 후 문제를 풀 수 있었다.

• 회의의 수량(N)을 입력 받는다.
• 회의의 수량 만큼을 반복하여 각각 시작 시간과 종료 시간을 튜플로 받아온 후 이를 모두 하나의 리스트에 저장한다.
• 회의 수량(cnt)과 종료 시간(end)을 0으로 초기화한다.
• 리스트 내 튜플의 종료 시간을 기준으로 정렬 후, 시작 시간을 기준으로 다시 정렬한다.
• 반복문을 통해 리스트 내 튜플의 요소를 호출하고, 호출한 시작 시간(s)이 종료 시간(end)보다 크거나 같을 경우 회의 수량을 1 증가시키며, 종료 시간을 호출한 시작 시간으로 대체한다.
• 반복이 종료되면 회의 수량을 출력한다.

위 가정 사항 중 "리스트 내 튜플의 종료 시간을 기준으로 정렬 후 시작 시간을 기준으로 다시 정렬한다." 라는 규칙을 세우는 데에 꽤 오랜 시간이 걸렸다. 이러한 항목을 세우는 이유는 아래와 같다.

• 시작 시간을 기준으로 정렬해보자. 그러면 가장 첫 번째 회의의 정보는 (0, 6)이 될 것이며, 가능한 회의는 (0, 6), (8, 11) (12, 14)로 총 3개의 회의가 가능할 것이다.
• 반대로 종료 시간을 기준으로 정렬해보자. 그러면 가장 첫 번째 회의의 정보는 (1, 4)가 될 것이며, (1, 4), (5, 7), (8, 11), (12, 14)로 총 4개의 회의가 가능할 것이다.
• 그러나, 종료 시간을 기준으로만 정렬했을 때에 한 가지 문제가 발생한다. 만약, (4, 4)가 주어진 정보에 포함되어 있을 때를 가정해보자. 종료 시간을 기준으로 정렬한 리스트의 요소 중 일부가 [..., (4, 4), (1, 4), (5, 7), ...]일 때 (4, 4)가 (1, 4) 보다 앞에 있을 경우가 존재하며, 이 경우 (4, 4)는 회의 가능 횟수에 포함이 되지 않는다.
• 따라서, 종료 시간을 기준으로 정렬 후 시작 시간을 기준으로 다시 정렬해주어야 한다. 즉, [..., (4, 4), (1, 4), (5, 7), ...]에서 시작 시작을 기준으로 다시 정렬하면 [..., (1, 4), (4, 4), (5, 7), ...]이며, (1, 4), (4, 4) 모두 회의 가능 횟수에 포함시킬 수 있다.

이를 코드로 나타내면 아래와 같다.

cnt = end = 0

lst = sorted([tuple(map(int, input().split())) for _ in range(int(input()))], key=lambda x: (x[1], x[0]))

for s, e in lst:
    if s >= end:
        cnt += 1
        end = e

print(cnt)

lambda 함수를 사용하여 입력받은 회의 정보들을 종료 시간(x[1])을 기준으로 먼저 정렬 후 시작 시간(x[0])을 기준으로 다시 정렬해주도록 하였다. 이 코드의 메모리는 50,848 KB이며, 시간은 4,820 ms이다.