알고리즘 유형 : 그리디(greedy)
풀이 참고 없이 스스로 풀었나요? : △ (테스트 케이스 참고)
https://www.acmicpc.net/problem/1931
SOLVE 1
그리디 풀이
import sys
input = sys.stdin.readline
N = int(input())
meet = [tuple(map(int, input().split())) for _ in range(N)]
meet.sort(key = lambda x: (x[1], x[0]))
count = 1 if meet[0][1] != 0 else 0
compare = meet[0][1]
for idx in range(1, N):
if compare <= meet[idx][0]:
count += 1
compare = meet[idx][1]
else:
continue
print(count)SOLVE 2
DP 풀이(시간 초과)
import sys
input = sys.stdin.readline
N = int(input())
meet = [tuple(map(int, input().split())) for _ in range(N)]
meet.sort(key = lambda x: (x[1], x[0]))
DP = [0]*N
DP[0] = 1
for idx in range(1, N):
sub = 0
for i in range(idx-1, -1, -1):
if meet[idx][0] >= meet[i][1]:
sub = DP[i]
break
DP[idx] = max(sub+1, DP[idx-1])
print(DP[N-1])SOLVE 1) 풀이 요약 (그리디 풀이)
-
회의 시간 튜플들을 종료 시간을 기준으로 정렬한다. 이 때, 두 번째 키로는 시작 시간을 기준으로 정렬한다.(뒤에서 설명)
-
직관적으로 보면, 무조건 종료 시간이 가장 빠른 것을 우선으로 계속 뽑는다. 최대 회의 개수를 구하는 건데, 회의 시간 리스트를 처음부터 쭉 for를 돌면서 아까 그 규칙으로 뽑아주면, 종료 시간 기준 오름차순 정렬된 상태이므로, 만약 2 4를 뽑았다면, 뽑은 회의 외의 남은 모든 회의는 종료 시간이 4 이상이라서, 시간이 2 4와 겹치거나 안 겹치거나(시작 시간이 4 이상) 둘 중 하나이다.
-
위 내용에 따르면 왠지 그리디 알고리즘으로 최적해를 구하면 그게 일반해가 될 것 같다. 구현은 그냥 인덱스 1부터 끝까지 for를 돌면서, prev(가장 최근에 뽑은 회의의 종료 시간)보다 현재 순회 중 인덱스에 해당하는 회의의 시작 시간이 더 크거나 같다면, 카운트 +1 하고 prev에 회의의 종료 시간을 새로 기록해준다. 그 후 카운트 출력. 끝!
-
한편, 처음에 회의 시간 튜플들을 종료 시간 기준으로만 정렬하면 문제가 발생한다.
시작 시간은 같은데 종료 시간이 같은 다수의 회의의 경우, 예를 들어
6 8
8 11
11 11
이렇게 입력이 들어오면 정렬 했을 때 저 형태로 정렬이 되어있으므로 코드를 따라가보면 문제 없이 잘 된다. 답은 3!
그런데,
6 8
11 11
8 11
이렇게 들어오면?
코드를 따라가보면, 6 8에서 카운트 +1 하고 prev = 10이다. 다음 차례에서 11 11의 11과 prev를 비교한다.
11이 더 크므로 카운트 +1하고 prev = 11. 다음 차례에서 8 11의 8이 prev보다 작다! 그러므로 if를 벗어나고 카운트와 prev가 갱신되지 않고 답은 2가 되어버린다. 이렇듯 종료 시간이 같고 시작 시간이 다른 경우에, 위치 관계에 따라 답이 달라짐을 알 수 있다. 따라서 꼭 정렬 두 번째 key로 시작 시간을 설정해주도록 하자.
SOLVE 1) 배운 점, 부족했던 점
- 시작 시간을 두 번째 키로 정렬해주는 걸 처음엔 생각도 안했고, 제출해보니까 틀렸다고 떴다. 계속 생각해보다가 테스트케이스 여러개 직접 만들어보기도 귀찮고 너무 번거로워서 테스트케이스를 검색해보고 다른 사람이 고안해 낸 테스트케이스 참고해서 미흡한 부분을 찾았다.
그런데 생각해보니 코딩테스트를 준비하는 입장인데, 코딩테스트에서 이런 비슷한 이유로 틀리게 되면, 그 때는 스스로 테스트케이스를 생각해내서 직접 해보고 수정을 해야할텐데, 그렇게 생각하면 테스트케이스도 바로 검색해보지말고 시간을 들여 틀린 점을 찾아본 후, 오랫동안 못 찾으면 그때서야 검색을 해보는 식으로 공부를 해야 좋을 것 같다.
