BOJ 1931번 -회의실 배정

 

그리디 알고리즘 문제를 풀기 위해서는, 최적의 해결 방법을 찾아야 한다.
최적의 풀이 방법을 생각해내지 못하고, 완전탐색으로 억지로 풀고자 한다면 시간 초과가 날 수밖에 없다.

최초에 이 문제를 풀면서도, 단순 정렬만을 하고 완전탐색으로 풀었다가 시간초과의 덫을 빠져나올 수 없었다.

하지만 이내 좋은 방법을 찾아내어, 시간 초과 문제를 해결할 수 있었다.

 

import sys
input = sys.stdin.readline

lst = []
for _ in range(int(input())):
    lst.append(list(map(int,input().split())))
lst.sort(key=lambda x : (x[0],x[1]))

time = []
for i in range(len(lst)):
    res = []
    for j in range(len(lst)-i):
        if len(res) == 0:
            res.append(lst[i])
        elif lst[i+j][0] >= res[-1][1]:
            res.append(lst[i+j])
    time.append(len(res))

print(max(time))

최초의 풀이 방법. 모든 경우의 수를 탐색하여 리스트에 추가하고, 해당 리스트에서 최댓값을 찾는

매우 비효율적인 방법이었다. 당연히 시간초과다.

 

import sys
input = sys.stdin.readline

lst = []
for _ in range(int(input())):
    lst.append(list(map(int,input().split())))
lst.sort(key=lambda x : (x[0],x[1]))

visited = [False]*len(lst)

time = [0]
for i in range(len(lst)):
    res = []
    if visited[i] != True:
        if len(lst[i:])<=len(lst)//2:
            break
        else:
            for j in range(len(lst)-i):
                if len(res) == 0:
                    res.append(lst[i])
                elif lst[i+j][0] >= res[-1][1]:
                    res.append(lst[i+j])
                    visited[i+j] = True
    time.append(len(res))

print(max(time))

몇가지 방법으로 탐색의 경우의 수를 줄였다.

이미 두번째 방문한 적이 있는 노드를 첫번째 탐색 노드가 되는 경우를 없앴다.

뿐만아니라 최초 입력받은 리스트의 절반을 탐색하면, 더이상 탐색하지 않게 제한했다.

두 번째 방법의 경우, 설령 시간 초과 문제를 해결할 수 있더라도 반례가 나올 수밖에 없는 방법이었다.

하지만, 최소한 시간 단축을 할 수 있을지 궁금하여 넣어봤다.

 

물론 위의 방법만으로는 시간을 줄일 수는 없었다.

for문을 이중으로 겹쳐서 쓰는 한, 크게 보아 O(N*N)의 시간복잡도를 벗어날 수는 없었다.

 

그러던 중, 좋은 방법을 생각해냈다.

기존에 입력받은 배열의 정렬 순서를 바꾸는 것이다.

 

최초의 정렬 방법은 다음과 같았다.

lst.sort(key=lambda x:(x[0],x[1]))

이 경우, 리스트의 배열 순서는 다음과 같다.

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

하지만, 앞자리가 아닌 뒷 자리부터 정렬한다면 다음과 같은 결과를 얻을 수 있다.

lst.sort(key=lambda x:(x[1],x[0]))

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

자연스럽게, 가장 먼저 시작하면서 가장 먼저 끝나는 회의가 무엇인지를 파악할 수 있게 된다.

그렇다면 loop문을 이중으로 돌릴 필요도 없게 된다.

 

import sys
input = sys.stdin.readline

lst = []
for _ in range(int(input())):
    lst.append(list(map(int,input().split())))
lst.sort(key=lambda x : (x[1],x[0]))

cnt = 0
res = -1
for i in lst:
    if i[0] >= res:
        cnt += 1
        res = i[1]

print(cnt)

res에 -1이 아니라 0을 넣어도 크게 상관은 없을 것 같다.

 

해당 방법을 사용하게 된다면, 전체 배열을 한번만 돌아도 최적의 경우를 찾을 수 있게 된다.