[Baekjoon] 1931 - 회의실 배정 Greedy (Python)

[Baekjoon] 1931 - 회의실 배정 (Greedy)

---

🧐 문제 설명

---

😍 나의 풀이

[프로그래머스] LEVEL3 단속카메라 문제와 거의 유사한 문제다. Greedy 알고리즘 문제를 더 풀이하고 싶어서 백준에서 탐욕 알고리즘을 사용하는 대표 문제 몇 가지를 풀어봤다.

이 문제는 "어떻게 하면 회의실 배정을 최대한 많이 할 것 인가?"에 대한 문제를 Greedy 하게 해결하는 것이 목표이다.

회의실 배정을 많이 하려면, 회의가 끝나자마자 새로운 회의가 회의실에서 진행되어야 한다.

→ 회의 종료 시간을 기준으로 회의 시간들을 정렬해준다. 종료 시간이 같다면, 시작 시간이 빠른 것부터 회의가 가능한 지 탐색해야 하기 때문에 2순위로 회의 시작 시간으로 한 번 더 정렬

이 로직이 완성되고 나면, 그 후로는 회의 시작 시간이 마지막 회의 종료 시간보다 크면(→ 회의가 진행되지 않아 회의실 사용 가능함) 회의실을 count +1 해주고 회의 끝나는 시간을 회의 종료 시간으로 초기화해준다.

n = int(input())
meeting = []
answer = 0
last_meeting_end = 0	# 마지막으로 회의가 끝나는 시간
    
for i in range(n):
    start, end = map(int, input().split())
    meeting.append([start, end])

meeting = sorted(meeting, key=lambda x:(x[1],x[0]))	
# 종료 시간 1순위, 시작 시간 2순위 순으로 회의 시간 정렬
        
for i in meeting:
    if i[0] >= last_meeting_end:	
    #회의 시작 시간이 마지막으로 회의 끝난 시간보다 크면
        answer += 1	# 회의실 이용
        last_meeting_end = i[1]

---

🥇 Today I Learn

백준 처음 풀이해봤는데 아직 익숙하지 않아서 그런가 프로그래머스보다 불편한 것 같다... 프로그래머스 위주로 풀이하고 알고리즘 종류별로 풀이하고 싶을 때 백준으로 더 풀이해야겠다.

아무튼 Greedy는 어떻게 하면 가장 최고의 선택을 할 수 있을지 생각부터 하는 게 우선!! 모르겠으면 정렬을 생각해보자