한 개의 회의실이 있는데 이를 사용하고자 하는 n개의 회의들에 대하여 회의실 사용표를 만들 려고 한다. 각 회의에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하 면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한번 시작하면 중간에 중 단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.
처음에는 문제를 이분탐색으로 접근하였다. n(1<=n<=100,000)이 주어진다. 이므로 이중 반복문 사용하면 시간초과도가 뜰게 자명했기 떄문이다. 내가 처음에 푼 코드는 다음과 같다.
N = int(input())
conference = [list(map(int, input().split())) for _ in range(N)]
start = end = []
for i in range(len(conference)):
start.append(conference[i][0])
end.append(conference[i][1])
#conference.sort()
conference.sort(key = lambda x: (x[1], x[0]))
#람다식 사용해서 key에서 2번째 값을 기준으로 오름차순 정렬
#print(conference)
lt = min(start)
rt = max(end)
#print(lt, rt)
while True:
tmp = conference[0]
cnt = 1
mid = (lt + rt) // 2
# print(mid)
# print(f'tmp:{tmp}')
# print(f's:conference {conference}')
for x, y in conference:
#print(x, y)
if tmp[1] <= x:
cnt += 1
tmp = x, y
elif tmp[0] <= x and tmp[1] >= y:
tmp = x, y
#print(f'cnt:{cnt}')
#print(f'e:conference {conference}')
if cnt < mid:
rt = mid - 1
else:
res = cnt
lt = mid + 1
if lt > rt:
break
print(res)
# cnt = 0
# et = 0
# for x, y in conference:
# if x >= et:
# cnt += 1
# et = y
# print(cnt)
'''
5
1 4
2 3
3 5
4 6
5 7
'''
Greedy Algorithm:
문제를 풀어나가는 과정(단계)에서 이 단계에서 가장 좋은게 무엇인지를 판별해서 가장 좋은 것을 선택함. "정렬"하고 나서 차례 차례 선택해 나는게 그리디 알고리즘의 문제접근 방법!
cnt = 0
et = 0
for x, y in conference:
if x >= et:
cnt += 1
et = y
print(cnt)
(x, y)로 튜플로 리스트 값이 주어져 있을 때, 만약 x가 아닌 y값을 기준으로 오름차순 정렬을 하고 싶다면,
람다식을 써야한다.
conference.sort(key = lambda x: (x[1], x[0]))
이 코드식은 외워야할 것 같다.(유용하다고 강사님께서 말씀하셨다.)
결정 알고리즘과 그리디 알고리즘의 유형을 어떻게 구분해야할지 아직 모르겠다.
좀더 문제를 풀면서 접근해봐야겠다.