[Python-CodingTest] 4-5. 회의실 배정 (그리디 알고리즘)

회의실 배정

문제 정리

입력

5 // n
1 4 //1번째 회의: 시작 종료
2 3 //2번째 회의: 시작 종료
3 5 //3번째 회의: 시작 종료
4 6 //4번째 회의: 시작 종료
5 7 //5(=n)번째 회의: 시작 종료

처리 과정

1. 튜플 형태로 회의 시간 입력받기
2. 최대한 많은 회의를 해야하니까 종료 시간을 기준으로 오름차순 정렬 (빨리 시작해도 늦게 끝나면 안됨, 빨리 끝나는게 우선!)
3. 튜플에서 for문 돌면서 지금 회의의 종료 시간이 다음 회의의 시작시간보다 작거나 같으면 다음 회의 가능

출력

3

풀이

import sys
sys.stdin = open("./input/in5.txt", "rt")

meeting=[] # 빈 리스트
n=int(input())
for i in range(n):
    start,end=map(int,input().split())
    meeting.append((start,end)) # 리스트에 튜플 형태로 넣기

# 회의를 최대한 많이 하기 위해서는 x[1](종료 시간) 기준으로 오름차순 정렬
meeting.sort(key=lambda x : (x[1],x[0]))
# meeting.sort() # 기본적인 sort()는 튜플의 x[0](시작 시간)을 기준으로 오름차순 정렬

end_time=0 # 회의가 끝나는 시간
cnt=0 # 가능한 회의의 수

# 튜플에서의 for문
for s,e in meeting:
    if s>=end_time: # 다음 회의를 할 수 있음
        end_time=e # 다음 회의가 끝나는 시간은 e
        cnt+=1

print(cnt)

정리

• 그리디는 대부분 “정렬”과 동반됨!
• 리스트에 튜플을 넣기: lst=[], lst.append((a,b))
• 튜플의 첫번째 요소(x[0]) 기준 (오름차순) 정렬: lst.sort()
• 튜플의 두번째 요소(x[1]) 기준 (오름차순) 정렬: lst.sort(key=lambda x: (x[1],x[0]))

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기