https://www.acmicpc.net/problem/14988
문제요약
- (방문한 가게 순서, 파는 물건이 주어짐) (10만개)
- 구매한 물건이 순서대로 주어짐 (10만개)
- 가능한지? 유일한지? 여러개인지? 불가능한지 판단
접근법
- 위상정렬 비슷하기도 하고
- 구매한 물건을 파는 가게 정보를 모음
- 모은 가게 정보가 값이 증가하는 방향으로 배치가 되는지 판단
- 예를들어 문제의 3번째 예시는 다음과 같이 표현 가능
tomatoes [0, 1, 2]
cucumber [0, 2]
salad [2]
mustard [1, 2]
salt [0, 2] - 0(처음)->0(0이상)->2(0이상)->2(2이상)->2(2이상) 순서를 만족해야함
- 이전배열과 현재배열을 비교하는 방식으로 접근해봄
- cucumber를 보면
- [0] 은 [0]만 가능
- [2] 는 [0],[1],[2]가 가능
- 누적이 발생하는것을 활용해서 접근
newbieski