이번 문제는 구현 자체는 쉬웠지만 정답에 이르는 논리를 떠올리기가 어려웠다. 정작 떠올리고 나서는 lambda 함수를 사용하여 간단하게 구현할 수 있었다. 이번 문제처럼 순간순간 최적의 답을 도출하겠다는 유형을 그리드 유형이라고 한다✨
문제
한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.
입력
첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.
11 1 4 3 5 0 6 5 7 3 8 5 9 6 10 8 11 8 12 2 13 12 14
출력
첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.
4
풀이 과정
이번 문제에서 회의를 최대한으로 하기 위해 가장 중요한 논리는 2가지였다.
ⓐ 회의가 끝나는 시간이 빠른 것을 우선할 것
ⓑ 회의가 끝나면, 가까운 시간 내에 다른 회의가 시작될 것
1. 입력 값 받기
N = int(input()) list_meeting = [] for i in range(N): x, y = map(int, input().split()) list_meeting.append((x, y))먼저 회의의 총 횟수 N을 int형으로 받아 저장하였고,
N개만큼 주어지는 회의 시간들을 저장하기 위해 list_meeting 리스트를 만들었다.
리스트에는 (x, y)형태로 회의 시작시간과 끝 시간이 저장된다.
2. 리스트 순서 정렬하기
list_meeting.sort(key = lambda x : x[0]) list_meeting.sort(key = lambda x : x[1]) --> list_meeting.sort(key = lambda x : (x[1], x[0]))로 줄일 수 있음ⓐ list_meeting에 저장된 값들을 먼저 회의 끝 시간을 기준으로 정렬한 채로,
ⓑ 회의 시작 시간이 빠른 순서의 리스트를 얻고 싶다.위에서 언급한 2가지 논리에 따라서 리스트를 정렬하면 손쉽게 정답을 도출할 수 있다.
따라서 sort와 lambda 함수로 회의 시작 시간으로 한 번, 회의 끝 시간으로 한번 정렬하였다.※ lambda 함수를 사용하면 key = lambda x : (a, b) 형태로 정렬을 한 번에 2번 진행할 수 있었다.
3. 회의 수 출력하기
meeting = 0 end_time = 0 for x, y in list_meeting: if x >= end_time: end_time = y meeting += 1 print(meeting)회의의 총 갯수를 출력해주기 위해서 meeting 변수를 정의하였다.
정렬된 list_meeting에 들어있는 시작 시간 x와 끝 시간 y를 활용하여
x가 end_time보다 크다면 y가 end_time이 되면서 meeting이 1개 늘어나는 코드를 작성하였다.
- 답안
# 1. 입력 설정
N = int(input())
list_meeting = []
for i in range(N):
x, y = map(int, input().split())
list_meeting.append((x, y))
# 2. 회의시간 정렬(끝나는시간 -> 시작시간 순)
list_meeting.sort(key = lambda x : x[0])
list_meeting.sort(key = lambda x : x[1])
--> list_meeting.sort(key = lambda x : (x[1], x[0]))로 줄일 수 있음
# 3. 최대 회의 수 출력
meeting = 0
end_time = 0
for x, y in list_meeting:
if x >= end_time:
end_time = y
meeting += 1
print(meeting)*모든 문제의 저작권은 백준 온라인 저지(https://www.acmicpc.net/) 원작자에게 있습니다.
백준 1931번(https://www.acmicpc.net/problem/1931)
