테스트 예제 2
•
Greedy 알고리즘을 적용하여 최적의 수강신청 스케줄을 알아내는 알고리즘을 작성해야 함.
•
가천대학교 홍길동 학생이 KEA 강의를 수강하기 위해 강의 스케줄을 체크 및 조율하고 있음. 10개의 과목들 중 최대한 많이 들으려고 조율하고 있음. 따라서 강의시간이 서로 겹치면 안되기 때문에 최적의 강의시간을 산출해야 함. 입력조건은 튜플형태로 입력됨.
•
해당 학기의 수업 리스트는 아래와 같음.
[(4, 8), (3, 5), (2, 4), (1, 4), (8, 10), (6, 8), (5, 7), (4, 5), (5, 8), (9, 11)]
•
상위 수업리스트의 형태에서 각 튜플의 0번째는 강의 시작교시를 의미하고 1번째는 종료교시를 의미함. 예를 들어 첫번째 튜플 인덱스인 (4, 8)의 강의를 보면 4교시에 시작하고 종료는 8교시에 함.
•
또한 (8, 10)강의와 (6, 8)강의를 보면 시작교시와 종료교시가 겹침. 이럴 경우에는 두 강의 수강은 불가능한 것으로 간주함.
입력 조건
튜플형식의 [(4, 8), (3, 5), (2, 4), (1, 4), (8, 10), (6, 8), (5, 7), (4, 5), (5, 8), (9, 11)]
출력 조건
겹치지 않고 최적의 강의시간을 산출해야 함.
출력 예시
[(2, 4), (5, 7), (8, 10)]
문제 해결 아이디어
시작 교시를 기준으로 리스트를 정렬하고, 선택 강의의 종료 교시에 따라 겹치지 않게 정렬해야함.
시간 복잡도
→ 강의 리스트를 정렬하는 부분이 가장 오래걸림
코드
lecture_list = [(4, 8), (3, 5), (2, 4), (1, 4), (8, 10), (6, 8), (5, 7), (4, 5), (5, 8), (9, 11)]
lecture_list.sort(key=lambda x: x[1]) # 강의 리스트를 종료 시간를 기준으로 정렬
optimal_list = [] # 최적 시간표 리스트 초기화
end = 0
for i in lecture_list:
start, finish = i
if start > end: # 현재 강의의 시작 교시가 이전 강의의 종료 시간보다 뒤일 경우
optimal_list.append(i)
end = finish
print(optimal_list)
Python
복사