문제
한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.
난이도
Silver 1
입력
첫째 줄에 회의의 수 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
n = int(input())
data = [tuple(map(int,sys.stdin.readline().split())) for _ in range(n)]
len = [data[i][1]-data[i][0] for i in range(n)]
len_dic = dict()
for i in range(n):
len_dic[data[i]] = len[i]
for i in range(n-1):
max_ = max(data[i][1], data[i+1][1])
time_ = [1] * (max_+1) # 회의 최대 시간을 담은 리스트. 1 이면 회의 가능
sorted_data = sorted(len_dic.items(), key = lambda item: item[1])
count = 0
# 회의 가능여부 판단 함수
def isOK(data, start, end):
for i in range(start, end+1):
if data[i] == 1:
pass
else:
return False
return True
for i in range(n):
start = sorted_data[i][0][0]
end = sorted_data[i][0][1]
if isOK(time_, start, end): # 회의가 가능하면
count += 1
for j in range(start+1, end):
time_[j] = 0
print(count)수정한 코드
import sys
N = int(input())
time = []
for _ in range(N):
start, end = map(int,sys.stdin.readline().split())
time.append([start, end])
time = sorted(time, key=lambda a: a[0]) # 시작 시간을 기준으로 오름차순
time = sorted(time, key=lambda a: a[1]) # 끝나는 시간을 기준으로 다시 오름차순
last = 0 # 회의의 마지막 시간을 저장할 변수
conut = 0 # 회의 개수를 저장할 변수
for i, j in time:
if i >= last: # 시작시간이 회의의 마지막 시간보다 크거나 같을경우
conut += 1
last = j
print(conut)느낀점
우선 이 문제는 그리디 문제이다.
현재 상황에서 가장 최선의 접근법을 찾는 방법에는 두 가지가 있는 것 같다.
- 빨리 끝나는 회의 순서대로 정렬 후 시작 시간이 빠른 순서대로 한번 더 정렬
- 절대적인 회의 시간(간격)이 짧은 순서대로 정렬
처음 짠 코드에서는 2번 방법으로 접근했었는데, 이 접근도 틀린 건 아니지만 계속해서 에러가 뜨고 코드 또한 복잡해지는 것 같아 구글링을 하다가 1번 접근법을 통한 코드가 더욱 깔끔하고 직관적인 것 같아 수정하였다.
또한 수정한 코드에서 만약 입력을 input()으로 받을 경우 시간 초과가 뜨기 때문에 가급적 sys.stdin.readline()을 사용하는 습관을 들이는 것이 좋을 것 같다.
