[BOJ] 2531번: 회전 초밥

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

문제가 뭔가 익숙해서 봤더니 2012년 KOI 지역본선 기출이네요. 당시에는 못풀어냈던 것 같습니다ㅎㅎ..

Naive하게 문제를 풀려고 한다면 O(Nk)로 풀이가 가능합니다. 요새 컴퓨터가 좋아져서 O(Nk)로도 통과가 될 것 같긴한데, 원래의 의도는 O(N+k) 풀이입니다.

시간복잡도를 내리기 위해 i번 초밥이 현재 보고 있는 접시의 범위 내에서 몇 개가 있는지를 저장하는 배열을 하나 둡니다.(코드 상의 kind 배열) 그리고 현재 초밥의 종류의 갯수를 tot라는 변수에 저장해두고, 초밥의 추가/삭제를 kind 값을 1 증가 / 1 감소하는 것으로 처리합니다. 이 때 이전에 없던(=kind의 값이 0이던) 초밥이 추가되거나 이전에 단 1개 있던(=kind의 값이 1이던) 초밥이 제거될 경우 tot를 1 증가 / 1 감소시킵니다.

이러한 방법으로 O(N+k)에 풀이가 가능합니다.

https://github.com/blisstoner/BOJ/blob/master/2531.cpp