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

문제 링크 : https://www.acmicpc.net/problem/1931

풀이 코드

---

from collections import defaultdict
conf_room = defaultdict(list)

N = int(input())

first_st = 2**31
last_ed = 0

for _ in range(N):
    st, ed = map(int, input().split())
    if conf_room[st]:
        temp = conf_room[st][-1]
        if st == ed:
            conf_room[st] = [ed] + conf_room[st]
        elif ed < temp :
            conf_room[st] = conf_room[st][:-1] + [ed]
        elif ed > temp and temp == st:
            conf_room[st].append(ed)
    else:
        conf_room[st].append(ed)
    
    if first_st > st :
        first_st = st
    if last_ed < ed :
        last_ed = ed

num_conf = 0
temp_ed = 2**31

for time in range(first_st, last_ed+1, 1):
    if time == temp_ed:
        num_conf += 1
        temp_ed = 2**31
    if conf_room[time]:
        while True:
            if conf_room[time]:
                if temp_ed > conf_room[time][0]:
                    temp_ed = conf_room[time][0]
            else:
                temp_ed = 2**31
                break
            if temp_ed != time:
                break
            else:
                del(conf_room[time][0])
                num_conf += 1
                temp_ed = 2**31

print(num_conf)

풀이 해설

---

회의 시작시간을 키(key)값으로, 끝나는 시간의 리스트(list)를 값(value)으로 갖는
딕셔너리를 이용한 문제 풀이를 진행하였습니다

입력받은 시간의 회의에 대해

1. 시작 시간과 동일한 종료 시간을 입력받을경우 무조건 추가
2. 기존에 갖고있던 종료 시간보다 더 빠른 종료시간을 가질 경우 업데이트 를 함으로써 모든 값을 갖지 않고 풀이를 진행할 수 있도록 하였습니다

위 방식을 통해 구성된 딕셔너리를
입력받은 시간의 최소 시작 시간(first_st) 부터 마지막 종료 시간(last_ed)까지
전체 탐색을 진행하며
해당 시간에 존재하는 회의 리스트를 한 개 씩 제거해나가며 카운트 하는 방식으로 풀었습니다