파이썬 백준 1931번
실버1
https://www.acmicpc.net/problem/1931
문제 보기
분류 그리디 알고리즘
문제 풀기
회의 시간이 겹치는 복수의 회의에서 늦게 끝날수록 전체 횟수가 늘어나는데 유리하다. 이를 기준 삼아 끝나는 시각을 오름차순으로 만들어야 한다. 그리고, 시작 시각의 경우 이전에 진행 중인 또는 진행된 회의의 끝나는 시각과 비교를 하게 되기에 시작 시각도 오름차순으로 정렬이 되어야 한다.
이 두 조건을 만족해야 하는데 최종 기준은 회의 끝나는 시각으로 결정되기 때문에 시작 시각인 timetable.sort(key = lambda x : (x[0])) 가 먼저 오름차순 정렬이 되고, 그 후, timetable.sort(key = lambda x : (x[1])) 로 끝나는 시각을 오름차순 정렬하여 순서를 결정한다.
그리고, for 문을 돌리면서 if timetable[i][0] >= meeting_end: 다음 회의 시간이 현재 회의 시간과 겹쳐지지 않고 나중에 시작되는 경우를 if 문으로 만들게 된다. 다음 회의 시작 시각과 현재 회의 끝 시각을 비교하여 시작 시각이 클 때 (뒤에 올 때) 새로운 회의의 시작임을 count 할 수 있다.
코드 보기
import sys
inputdata = sys.stdin.readline
N = int(inputdata().strip())
timetable = []
for _ in range(N):
meeting = tuple(map(int, inputdata().split()))
timetable.append(meeting)
timetable.sort(key = lambda x : (x[0]))
timetable.sort(key = lambda x : (x[1]))
count = 0
meeting_end = 0
for i in range(len(timetable)):
if timetable[i][0] >= meeting_end:
count += 1
meeting_end = timetable[i][1]
print(count)
추가 하기
질문 페이지에 올라온 반례를 통해 코드를 고쳐가며 중간 중간 프린트로 확인해본 코드
import sys
inputdata = sys.stdin.readline
N = int(inputdata().strip())
timetable = []
for _ in range(N):
meeting = tuple(map(int, inputdata().split()))
timetable.append(meeting)
print(f'timetable origin: {timetable}') #
timetable.sort(key = lambda x : (x[0]))
timetable.sort(key = lambda x : (x[1]))
print(f'timetable sorted: {timetable}') #
count = 0
meeting_end = 0
for i in range(len(timetable)):
if timetable[i][0] >= meeting_end:
count += 1
meeting_end = timetable[i][1]
print(f'timetable tuple: {timetable[i]}') #
print(count)
# 7
# 3 10
# 2 2
# 1 3
# 2 2
# 9 10
# 4 9
# 2 2
# timetable origin: [(3, 10), (2, 2), (1, 3), (2, 2), (9, 10), (4, 9), (2, 2)]
# timetable sorted: [(2, 2), (2, 2), (2, 2), (1, 3), (4, 9), (3, 10), (9, 10)]
# timetable tuple: (2, 2)
# timetable tuple: (2, 2)
# timetable tuple: (2, 2)
# timetable tuple: (4, 9)
# timetable tuple: (9, 10)
# 5
'공부하기 > 백준' 카테고리의 다른 글
[Python] 백준 풀기 2630 - 색종이 만들기 (0) | 2022.10.10 |
---|---|
[Python] 백준 풀기 1541 - 잃어버린 괄호 (0) | 2022.10.09 |
[Python] 백준 풀기 11047 - 동전 0 (0) | 2022.10.06 |
[Python] 백준 풀기 2231 - 분해합 (2) | 2022.10.05 |
[Python] 백준 풀기 2559 - 수열 (0) | 2022.10.04 |