1931번 회의실 배정

문제 출처 : https://www.acmicpc.net/problem/1931

사고과정

이 문제를 사실 이전에 풀어서 어느정도 아이디어를 도움받아 풀수 있지 않았나 싶다.

결국 몇 가지 회의만을 비교하여 도출할 수 있는 게 아니라 모든 회의를 고려하여 구현해야 정답이 도출 가능하다.

어떤 회의를 선택해야 할까?

회의 시작 시간을 기준으로 리스트를 sort 했을 때, 만약 어떤 회의가 0에 시작하여 6에 끝난다고 해보자. 바로 다음 회의를 가져왔을때 만약 이 회의가 4에서 시작하여 8에 끝난다고 하면 리스트에 1~3에 시작하는 회의는 존재하지 않는 것이다. 이를 연역적으로 생각해보면 그 다음 회의들은 무조건 4이상의 시간에 시작하게 되므로 만약 7에 시작하는 회의가 다음 값으로 들어왔을 때 첫 번째 회의 이후 세번째 회의는 진행 가능하지만 두번째 회의 이후 세번째 회의는 진행 불가능하다. 이를 일반화하여 생각하면 결국 회의가 빨리 끝날수록 이후의 회의들 중에 더 많은 회의를 진행할 수 있다. 왜냐!

다시 잘 살펴보면 두번째 회의 시작시간이 4였기 때문에 어차피 1~3에 시작하는 회의는 있을 수 없다. 마찬가지로 4~6인 회의들 또한 첫,두번째 회의와 동시에 진행할 수 없다. 하지만 6~8인 회의는 첫번째 회의를 택했을 경우에만 진행가능하다. 즉 빨리 끝난 걸 택하자.

현재 회의를 따로 빼서 c에 저장.
리스트에 회의들과 비교하여 이상적인 회의 진행방식 택.

오류 발생!
일반적인 부분은 통과하니까 예외처리가 제대로 되지 않았구나. 문제에서 (시작==끝 인 부분) 제시하여 이에 대한 부분 처리를 해야겠다.

내가 짠 로직에 (시작==끝)이 들어가면 어떻게 될까? 제대로 작동하는가?

1. c라는 회의의 시작시간에 존재할 때 -> count에 +1이 되고 기존 c는 유지되어야 하는데 c->(시작=끝)으로 바뀌어버림. Error!
2. c라는 회의의 중간시간에 존재할 때 -> 정상처리
3. c라는 회의의 종료시간에 존재할 때 -> 정상처리
4. (시작==끝) 뒤에 동일한 시작시간으로 들어올 때 -> 정상처리
5. 두번 이상 연속하여 존재할 때 -> 정상처리

import sys

N=int(sys.stdin.readline().rstrip("\n"))

conference = [tuple(map(int,sys.stdin.readline().rstrip("\n").split())) for _ in range(N)]
conference.sort(key = lambda x : x[0])
c =[conference[0][0],conference[0][1]]
count=1

for n in range(1,N) :
    #conference[0]는 증가형
    
    if c[1]<=conference[n][0]:
        count+=1
        c=[conference[n][0],conference[n][1]]
    elif conference[n][0]<c[1]:
        if c[0]==conference[n][0]==conference[n][1] :
            count+=1
            continue
        if conference[n][1]<c[1] :
            c=[conference[n][0],conference[n][1]]
print(count)

불변의 데이터라면 list보단 tuple을 사용하는 편이 시간, 공간 복잡도 측면에서 더욱 효율적임.