문제 풀이

1. 위상 정렬 문제
2. 그래프 형태 : 선수문제(부모) -> 후수문제(자식). 각 노드는 부모 노드를 0개 이상 갖는다.
3. 로직:
1) unsolved 상태의 문제 중에서 선수문제가 없는 노드는 candidates 에 저장한다.

2) candidates 에서 가장 쉬운 문제(번호가 작은 노드) v 를 solve 한다.

3) v 는 자식들과 연결 관계를 끊는다. 이후, 부모가 한명도 없는 자식 노드는 candidates 에 추가한다.

모든 문제를 다 풀때까지 (1), (2) 과정을 반복한다.

구현

- Graph: 각 Node는 자식 리스트(children)와 부모의 숫자(unsolvedParentNum)를 갖는다.
- candidates 구현 : 쉬운 문제 순으로 저장되야 하므로, priority queue 로 구현

문제 링크: https://www.acmicpc.net/problem/1766

문제 풀이

1. 슬라이딩 윈도우 문제
2. 풀이는 다음과 같다.

구현

1. eaten : 현재 먹을 수 있는 초밥 정보 : (초밥id, 초밥개수)
2. 먹을 수 있는 가짓수 계산: eaten에 들어있는 key 의 현재 개수, coupon이 존재 하는지 여부로 계산 가능
3. 다음 칸으로 이동할때,
 — left가 가리키는 초밥을 eatenMap 에서 하나 제거한다. 그리고 left 포인터 1 증가
 — right 을 1 증가 시킨다. 그리고 right이 가리키는 초밥을 eatenMap에 하나 추가한다.
4. 회전 구현 : index%belt.size
 — ex, IF 회전 초밥 벨트의 길이가 5, index 가 5라면, 0 번째 요소

문제 링크: https://www.acmicpc.net/problem/2531