[Python : 백준 1931] 회의실배정

문제

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

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

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

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

# 출력 예시
4

풀이

1. 최초 해시테이블을 이용한 접근

• 회의진행시간 (end-start)가 작은 순으로 정렬한다.
• 0~23시까지의 해시테이블을 만든다.
• 루프를 돌면서 해시테이블에 해당 시간이 사용됨을 표기한다.

N = int(input())
session = []
for i in range(N):
    session.append(list(map(int, input().split())))

session = sorted(session, key=lambda x: x[1]-x[0])
timetable = {i: 0 for i in range(24)}
count = 0

for start, end in session:
    if timetable[start] == 0 and timetable[end] == 0:
        count += 1
        for i in range(start, end+1):
            timetable[i] = 1

print(count)

런타임 에러가 발생했다. 해시 테이블 범위를 벗어난 참조가 일어난 것.
지문을 다시 읽어보니 시간이 0~23까지가 아니고, 무한하게 커진다.
아이고… 지문을 잘 읽고 다시 시작해보자.

2. 해시테이블 대신 리스트로 회의시간 저장

• 1번의 알고리즘에서 해시테이블을 리스트로 대체한다.
• 리스트에 회의시간을 저장시킨다!

N = int(input())
session = []
for i in range(N):
    session.append(list(map(int, input().split())))

session = sorted(session, key=lambda x: x[1]-x[0])
timetable = []
count = 0

for start, end in session:
    if start not in timetable and end not in timetable:
        count += 1
        timetable += list(range(start, end))

print(count)

이론상 그럴듯 했지만, 계속 시간초과가 발생했다.
설마 입력받는 루프까지 포함해서 2n 시간으로 계산하진 않을테고…
아마도 start not in timetable and end not in timetable 조회가
리스트 pop(n)처럼 오버헤드가 큰 것 같았다.
또한 저 방식 자체가 공간복잡도가 굉장히 클것이 예상되었기 때문에
다른 방법을 강구해야했다.

3. 문제 분류가 그리디 알고리즘인 것에서 힌트를 얻자.

• 그리디 알고리즘으로 분류된 문제다.
• 회의종료시간이 빠른 순서대로 정렬하고 루프를 돌리면 해결될 것이다.
• 단!! 회의시작 시간으로 우선 정렬하고 회의종료시간으로 다시 정렬해야한다.
  그렇지 않으면 (2,2) (1,2) 와 같은 반례가 생긴다.
• 다행히도 파이썬의 sorted()함수는 완전정렬이다.

N = int(input())
session = []
for i in range(N):
    session.append(list(map(int, input().split())))

session = sorted(sorted(session), key=lambda x: x[1])
count = 0
pre_end = 0
for start, end in session:
    if start >= pre_end:
        count += 1
        pre_end = end
        
print(count)

겨우 통과할 수 있었다.

확실히 백준 문제들이 난이도가 들쑥날쑥하고, 고려할 것들이 많다.
특히 프로그래머스랑 지문의 친절함이 많이 대조된다.

난이도는 내가 더 공부하면 되는거니까 불만은 없는데, 채점 시간에 불만이 많다.
테스트케이스가 얼마나 많길레 채점이 이렇게 오래걸리는지 모르겠다.
프로그래머스는 10초가 넘어가면 알아서 끊어주는데, 백준은 1~2분 채점은 우습게 돌아간다…;;