[1700] 멀티탭 스케줄링

https://www.acmicpc.net/problem/1700

1700번: 멀티탭 스케줄링

---

풀이 방법

핵심은 콘센트가 가득 차있을 경우 어떤 전기용품을 뺄지를 결정하는 것이다.

정답은 앞으로 사용하지 않을 기기 혹은 앞으로 사용할 예정인 기기로 가득 차있는 경우라면 그중에서 가장 나중에 사용할 기기를 빼면 된다.

 

질문게시판에 좋은 예제가 있어 해당 예제로 설명하면 다음과 같이 동작한다.

3 10
1 2 3 4 4 5 2 1 1 4

 

각 전기용품별 사용될 순서의 시기를 스택형태로 저장한다. 맨 아래는 콘센트의 상태.

콘센트가 가득 찰때 까지 전기용품을 할당한다. 초기의 1,2,3은 바로 할당된다. 할당됨과 동시에 각 전기용품에 해당하는 사용횟수는 차감된다.

4번 전기용품이 할당될 때, 콘센트에 할당 된 3번은 더이상 사용되지 않으므로 3번을 뺀고 4번을 할당하게 된다.

콘센트에 이미 할당된 기기가 사용될 경우 횟수를 차감한다.

5번이 할당될 때, 1,2,4의 할당 순서를 확인, 스택의 top이 가장 큰 번호를 가진 4번 전기용품이 콘센트에서 분리된다.

마지막으로 4번이 할당될때는 1,2,5 전부 더이상 사용되지않으므로 셋중 하나를 분리하면 된다.

---

정답 코드