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

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

• 이번 문제는 그리디로 구상하는 것을 실패해서 재귀함수로 완전탐색을 하려했으나 시간 초과가 나서 실패하였다. 반나절 정도 고민 후 포기하고 그리디로 푼 다른 분의 코드를 보고 참고하였다. 알고보니 구상이 어렵지 구현은 매우 쉬운 코드였다.

---

< 문제제목 > 

[문제]

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

[입력]

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

[출력]

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

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

---

• 맞는 코드는 맨 아래에 있습니다

아이디어

회의를 하나 선택 하고 조건에 맞는 다음 인덱스로 가서 다시 회의 선택 함수를 호출하는 재귀함수를 짜고자 하였다. 

틀린 코드와 틀린 이유

import sys
sys.setrecursionlimit(200000)

n = int(input())
meetings = []
for _ in range(n):
    meetings.append(tuple(map(int, input().split())))
# 시작으로 정렬
meetings.sort(key=lambda tup : tup[0])

max_cnt = 0
def select_meeting(i, prev_end_time, cnt):
    global max_cnt
    # 재귀 종료
    if i == n:
        # 최대 카운트 업데이트
        max_cnt = max(max_cnt, cnt)
        return
    # 현재 회의의 다음에 있는 회의들 각각에서 다시 함수 호출
    for next in range(i + 1, n):
        # 조건 확인
        if prev_end_time > meetings[next][0]:
            continue
        # 조건에 맞다면 함수 호출
        select_meeting(next, meetings[next][1], cnt + 1)
    # 재귀 종료조건으로 들어가지 못하는 경우를 위해 i에 n 전달 후 함수 호출
    select_meeting(n, prev_end_time, cnt)
select_meeting(-1, 0, 0)

print(max_cnt)

N은 최대 100000이고, 제한시간은 2초이므로 대충 1초에 1억번 계산이라고 했을 때 시간복잡도 O(NlogN)이면 될 것이라고 생각하였다. 그래서 for문의 범위에 i + 1을 주게 되면 O(NlogN)이 될 것이라고 생각하였는데 완전히 틀린 생각이었다. 사실 이 코드에 오기까지 너무 많은 시행착오가 있어서 정신이 오락가락한 상태였다. 결국 시간복잡도는 O(N^N)정도였던 것 같다.(스스로 계산한 거라 틀릴 수도 있습니다.) 그래서 완전히 접근 방식이 잘못되었다는 것을 깨닫고 이전에 다른 사람들이 풀었던 코드를 참고하였다.

풀이 및 코드

import sys
input = sys.stdin.readline
n = int(input())
meetings = []
for _ in range(n):
    meetings.append(tuple(map(int, input().split())))
# 시작시간을 첫 번째로 종료시간을 두 번째로, 순서대로 정렬
meetings.sort(key=lambda tup : (tup[0], tup[1]))

# 첫 번째 회의 종료시간 저장
prev_meeting_end = meetings[0][1]
cnt = 1
for i in range(1, n):
    # 새로운 회의 종료시간이 더 빠르다면 그 전 회의 대신 새로운 회의에 참석함.
    # 따라서 새로운 회의의 종료시간 저장
    if prev_meeting_end > meetings[i][1]:
        prev_meeting_end = meetings[i][1]
    # 그게 아니라면 시작시간 보기.
    # 회의 시작시간이 이전 회의 종료시간보다 늦거나 같다면 카운트 증가, 회의 종료시간 저장
    elif prev_meeting_end <= meetings[i][0]:
        cnt += 1
        prev_meeting_end = meetings[i][1]

print(cnt)

이것이 나의 정답 코드이다. 이전과 다르게 회의의 start, end로 정렬을 해준 후 이전 회의의 end 시간만을 이용하여 코드를 구현하였다. 다음 회의의 종료시간이 이전 회의의 종료시간보다 빠르다면 다음 회의를 선택하는 것이 맞으므로 그 종료시간을 저장해주었고, 만약 그게 아니라면 이제 이 회의를 선택할지 말지 결정해야한다. 이 회의의 시작시간이 이전 종료시간과 같거나 이후라면 회의를 선택해주었다. 이렇게 해서 시간복잡도가 O(N)인 코드로 구현 성공하였다.

 

이 문제를 풀고 난 후 내 친구 기찬이에게 풀어보라고 하였고, 슥삭슥삭 풀고 나서 코드를 서로 공유를 해보았다. 그런데 여기서 대단한 것을 발견하였다. 기찬이의 코드엔 새로운 회의의 종료시간이 더 빠를 때 처리해주는 부분이 없었다. 왜 그런가 살펴보았는데 기찬이는 end로 먼저 정렬 하고 그 후에 start로 정렬 하였다. 그렇게 되면 이미 end로 정렬이 되어있기 때문에 뒤의 회의가 앞의 회의보다 항상 늦게(혹은 동시에) 끝나는 것이었다. 그렇게 새로 고친 코드는 다음과 같다.

import sys
input = sys.stdin.readline
n = int(input())
meetings = []
for _ in range(n):
    meetings.append(tuple(map(int, input().split())))
# 이전 코드와 반대로 정렬했음.
# 종료시간으로 먼저 정렬하고 그 다음에 시작시간으로 정렬
meetings.sort(key=lambda tup : (tup[1], tup[0]))

# 첫 번째 회의 종료시간 저장
prev_meeting_end = 0
cnt = 0
for i in range(n):
    # 회의 시작시간이 이전 회의 종료시간보다 늦거나 같다면 카운트 증가, 회의 종료시간 저장
    if prev_meeting_end <= meetings[i][0]:
        cnt += 1
        prev_meeting_end = meetings[i][1]

print(cnt)

이 문제로 그리디 알고리즘이 무엇인지, 현재 상황에서 최선의 선택을 한다는 것이 무슨 의미인지 제대로 알게 되었다. 그리디 알고리즘은 구현만 잘 해낸다면 낮은 시간복잡도로 프로그램을 짤 수 있는 알고리즘인 것 같다.