문제
한 개의 회의실이 있는데 이를 사용하고자 하는 n개의 회의들에 대하여 회의실 사용표를 만들
려고 한다. 각 회의에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하
면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한번 시작하면 중간에 중
단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.
▣ 입력설명
첫째 줄에 회의의 수 n(1<=n<=100,000)이 주어진다. 둘째 줄부터 n+1 줄까지 각 회의의 정
보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다.
▣ 출력설명
첫째 줄에 최대 사용할 수 있는 회의 수를 출력하여라.
▣ 입력예제 1
5
1 4
2 3
3 5
4 6
5 7
▣ 출력예제 1
3
cf) 예제설명
(2, 3) , (3, 5), (5, 7)이 회의실을 이용할 수 있다.
풀이
n = int(input())
cnt = 0
time = []
for _ in range(n):
s, e = map(int, input().split())
time.append((s,e))
time.sort(key=lambda x:(x[1], x[0])) # x[1]을 1순위, x[0] 을 2순위로 해서 정렬
last = 0 # 회의의 마지막 시간을 저장
for i,j in time: # 시작시간, 끝나는 시간
if i >= last: # 회의를 할 회의의 시작시간이 현재 진행하고 있는 회의의 끝나는 시간보다 이후이면
last = j # 회의를 했으니 끝나는 시간 변경
cnt += 1
print(cnt)
설명
그리디 알고리즘 관련해서도 정리가 잘 안됐어서 문제 접근이 불가능 했다.
- 그리디 알고리즘: 미래를 생각하지 않고 현재 차례에서 최고의 답을 찾는 문제. 보통은 정렬로 찾음
** lambda 함수 - key 가 여러개 일 때 정렬 우선순위 정하기
- lambda 함수는 특정 요소를 기준으로 정렬의 기준을 정할 수 있다!
- x[1] 을 기준으로 정렬했다가 x[1]이 동일하다면 x[0]을 기준으로 정렬하는 식으로 우선순위를 정할 수 있음
time.sort(key=lambda x:(x[1], x[0])) # x[1]을 1순위, x[0] 을 2순위로 해서 정렬
<알고리즘 설명>
가장 빨리 끝나는 회의를 찾아야 회의를 많이 할 수 있다!!
1. 종료 시간을 기준으로 오름차순 정렬
2. 제일 처음부터 진행 가능한 회의들을 진행
3. 해당 종료시간 전에 시작하는 회의는 무시
'Coding Test > Python' 카테고리의 다른 글
| [백준] 구간 합 구하기 5 (0) | 2023.07.01 |
|---|---|
| [Python] 씨름 선수(그리디) (0) | 2023.06.29 |
| [프로그래머스] 바탕화면 정리 (0) | 2023.06.18 |
| [프로그래머스] 조건 문자열 (0) | 2023.06.14 |
| [프로그래머스] 더 크게 합치기 (0) | 2023.06.13 |