[백준][Greedy] 1931번 문제 - 회의실배정 python (200804)

1. 문제설명

즉, 여기서 중요한 거는 최대한 많은 회의실을 배정하게끔 알고리즘을 짜는건데 

나는 이걸 회의시간 길이가 짧은 친구들을 중심으로 정렬하면 되겠다고 생각했다. 

결론부터 말하자면, 이것은 틀린 접근... 

 

 

 

2. 풀이  - 총 3번의 시도 - 3) 번이 정답

 

1) 딕셔너리로 풀기, 시작 시점 기준 정렬 - 런타임 에러 (이렇게 풀면 안됩니다) 

 

import sys

N = int(input())
info_list = []
for idx in range(N):
    st,end = map(int, sys.stdin.readline().split())
    dur = end - st
    info_list.append((st,end,dur))

info_list = sorted(info_list, key = lambda x:(x[0],x[2],x[1]))
chk_dict = {}
min_end = 12129831209873109
idx =0

for info in info_list:
    st, end, dur = info[0],info[1],info[2]
    
    # 기존 딕셔너리 키 값에 추가 
    if min_end <= st:
        for key, values in chk_dict.items():
            if values[len(values)-1][1] <= st:
                values.append(info)
            else:pass
            
    # 시작 시점 - 딕셔너리 키 생성
    else:
        chk_dict[idx] = [info]
        if min_end > end:
            min_end = end
        idx+=1

print(max([len(val) for val in chk_dict.values()]))

 

각각 회의 시작 시간, 끝 시간, 진행 시간을 튜플로 저장해서 리스트에 담았고 

리스트에 정렬을 할때 우선순위가 1) 시작시간 2) 진행시간 3) 끝시간이 되도록 람다를 썼다. 

정렬 결과 [(0, 6, 6), (1, 4, 3), (2, 13, 11), (3, 5, 2), (3, 8, 5), (5, 7, 2), (5, 9, 4), (6, 10, 4), (8, 11, 3), (8, 12, 4), (12, 14, 2)]

 

# 시작시점 - 딕셔너리 키 생성

그리고 info_list 에서 각각의 info 를 꺼낸 뒤

해당 info 의 시작 시점이 min_end 값보다 작은 값이 나오면 (맨 처음 초기값 설정을 위해 min_end는 아예 큰값으로 때림) 

딕셔너리의 키로 생성했고 ( --> 각 회의의 시작 시점)

 

# 기존 딕셔너리 키 값에 추가 

min_end 값보다 크거나 같은 값이 나오면 

각각의 딕셔너리 키 값을 확인 한 다음에 끝 시점에 맞물리는 곳에 추가했다.

 

0 : [(0, 6, 6), (6, 10, 4), (12, 14, 2)]
1 : [(1, 4, 3), (5, 7, 2), (8, 11, 3), (12, 14, 2)]
2 : [(2, 13, 11)]
3 : [(3, 5, 2), (5, 7, 2), (8, 11, 3), (12, 14, 2)]
4 : [(3, 8, 5), (8, 11, 3), (12, 14, 2)]

 

 

결론 : 지옥의 구조 형태를 만들어버림, 시간 복잡도 이중 포문 ㅠ

 

 

 

2) 끝 시점을 기준으로 정렬해서 풀기 (컨셉은 맞음, 하지만 코드상에 오류 하나 발견)

 

시작 시점을 기준으로 정렬을 하는게 아니라, 끝 시점을 기준으로 정렬을 했어야 했다. 

끝 시점이 빠른 친구들을 먼저 배정하되, 해당 친구의 시작 시점이 이전 회의실 끝시간 보다 같거나 크면 ok 

그래서 다시 풀어보면, 

 

import sys

N = int(input())
info_list = []
for idx in range(N):
    sta, end = map(int, sys.stdin.readline().split())
    info_list.append((sta,end))
info_list = sorted(info_list, key = lambda x: (x[1], x[0]))

end_point = info_list[0][1]
chk = 1
select_time_list = []

for info in info_list:
    st, en = info[0], info[1]
    if (st >=  end_point):
        select_time_list.append(info)
        print(info)
        end_point = en
        chk+=1
        
print(chk)
print(select_time_list)

lambda 에서 key 를 x[1] x[0] 으로 설정해서, 튜플의 두번째 값 (끝나는 시점) 을 기준으로 먼저 오름차순 정렬이 되게끔 만들었다.

 

그리고 맨 처음 나오는 값을 첫 배정 회의다. 

(아까의 코드에 비해 훨씬 탐색 경로가 줄어든다, 아까는 n 개를 첫 배정 회의로 두고 이중 포문으로 모든 경우를 탐색했었음... ) 

 

배정된 회의를 새는 chk는 1 // 처음 끝 포인트는 첫 배정 회의의 끝시간 end_point 로 초기값 설정 

쭉쭉쭉 탐색하면서 배정 가능한 회의실이 등장할때마다 chk 값을 하나씩 늘림

 

어떤게 담기는지 확인하기 위해서 select_time_list 에 append 과정을 추가했는데, 

저거 굳이 안해도 됨 (답은 chk에 담기니까) 

 

-------------

 

하지만, 이것도 오답이었다. 왜냐면 

 

 

case 1.  11 1 4 3 5 0 6 5 7 3 8 5 9 6 10 8 11 8 12 2 13 12 14

case 2.  12 1 1 1 4 3 5 0 6 5 7 3 8 5 9 6 10 8 11 8 12 2 13 12 14

case 1.

chk : 4 // select_time_list: [(1, 4), (5, 7), (8, 11), (12, 14)] 로 원하는 답이 나오지만 

 

case 2.  (1에서 (1,1) 추가)

chk : 6 // select_time_list: [(1, 1), (1, 1), (1, 4), (5, 7), (8, 11), (12, 14)] 로  답이 나온다 

(정답은 5임, (1, 1) 이 중복된 것... ) 

 

맨 처음 문제에서 언급한 시작과 동시에 끝나버린 즉, 시작 = 끝 인 회의의 경우가 맨 앞에 나왔을 때, 

for 문을 통해 해당 값이 중복되어서 들어가버리게 된다.

 

맨 처음 select_time_list : [(1,1)] / 현재 end_point :1

for 문 시작

info_list[0] 의 시작점 1 == end_point

 --> select_time_list 에 append 되어버림 ;;; 

 

case 1 은 첫 회의가 시작 != 끝 이었기 때문에,  굳이 맨 앞의 회의를 빼주지 않아도, 당연히 넘어가는 알고리즘 이었다.

 

 

 

 

3) 끝 시점을 기준으로 정렬해서 풀기  + 시작==끝인 친구들까지 고려 (정답 정답 정답)

 

import sys

N = int(input())
info_list = []
for idx in range(N):
    sta, end = map(int, sys.stdin.readline().split())
    info_list.append((sta,end))
info_list = sorted(info_list, key = lambda x: (x[1], x[0]))

end_point = info_list[0][1]
chk = 1

for info in info_list[1:]:
    st, en = info[0], info[1]
    if (st >=  end_point):
        print(info)
        end_point = en
        chk+=1

print(chk)

 

따라서 info_list의 두번째 값부터 꺼내서 탐색하도록, info_list[1:] 로만 변경했더니 합격!

 

 

 

 

3. 정리

분명 저번 카카오 문제도 이렇게 풀었으면 런타임 에러를 해결 했을거라 생각한다. 

잊지말자, 시간 배정 최대한 많이 하는 알고리즘은, 끝 시간 기준으로 정렬해서 풀어야 한다는 사실을 

뭐만하면 .. 해쉬로... 푸는 버릇을... 없애보아....!