https://www.acmicpc.net/problem/1931
#Solution
두 가지 코드를 시도해보았다.
1. 시작시간을 lambda 함수로 오름차순 정렬한 뒤, 가장 뒤 회의 부터 가능한 maximum 회의 수를 출력하는 방법
2. 끝나는 시간 -> 시작 시간 차례로 오른차순 정렬한 뒤, 끝나는 시간이 가장 이른 시간 부터 차곡차곡 더해가는 방법
결국 빨리 끝나는 것 중 빨리 시작하는 순서(시작과 끝이 같은 경우의 수를 걸러줌)대로 집어 넣으면,
더 빠르게 답을 구해낼 수 있다.
1번은 자체적으로 만든 함수로 O(nlogn)이 걸린다(고 생각했지만 O(n^2)이다). 물론 답은 맞다(반례 있을 수도).
2번은 람다를 두 번 활용하는 함수로 O(nlogn)의 시간복잡도가 걸린다. 결론은 내장함수가 더 효율적이다.
1. 시간 초과 나는 코드
import sys
N = int(input())
meeting = []
for _ in range(N):
meeting.append(list(map(int, sys.stdin.readline().split())))
meeting = sorted(meeting, key = lambda x: [x[1], x[0]])
#뒤에서 부터 maximum 회의 수를 구해준다
max_meeting = [0 for _ in range(N)]
for i in range(1, N+1):
for j in range(i):
if i == 1:
max_meeting[-i] = 1
else:
if meeting[-i][1] <= meeting[-i+j][0]:
if max_meeting[-i] < max_meeting[-i+j] + 1:
max_meeting[-i] = max_meeting[-i+j] + 1
if not max_meeting[-i]:
max_meeting[-i] = 1
print(max(max_meeting))
2. 정답 코드
import sys
N = int(input())
meeting = []
for _ in range(N):
meeting.append(list(map(int, sys.stdin.readline().split())))
meeting = sorted(meeting, key = lambda x: [x[1], x[0]])
#빨리 끝나는 것 중 가장 빨리 시작하는 순서대로 더해준다.
max_meeting = 0
start = 0
for meet in meeting:
if meet[0] >= start:
start = meet[1]
max_meeting += 1
print(max_meeting)
'Programming [Python] > 백준 알고리즘 솔루션' 카테고리의 다른 글
#162 백준 파이썬 [2667] 단지번호붙이기 - BFS (0) | 2019.11.04 |
---|---|
#161 백준 파이썬 [1541] 잃어버린 괄호 (0) | 2019.10.31 |
#159 백준 파이썬 [12865] 평범한 배낭 - 냅색 알고리즘 (1) | 2019.10.31 |
#158 백준 파이썬 [9251] LCS (0) | 2019.10.28 |
#157 백준 파이썬 [2565] 전깃줄 - LIS (1) | 2019.10.28 |