[BOJ] 15961

less than 1 minute read

회전 초밥

15961번 https://www.acmicpc.net/problem/15961

투 포인터 알고리즘을 이용하는 문제입니다.
왼쪽과 오른쪽 포인터를 한칸씩 옮겨가면서
왼쪽의 초밥을 제외할 때, 제외한 초밥 종류의 cnt가 0이라면 kind를 -1해줍니다.
오른쪽의 초밥을 포함할 때, 포함한 초밥 종류의 cnt가 1이라면 kind를 +1해주고, 최댓값을 갱신합니다.
이렇게 한바퀴를 모두 돌아주면 되는데,
선형이 아니라 사이클로 되어있는 회전초밥이기 때문에 왼쪽과 오른쪽 포인터를 옮겨줄 때
ptr = (ptr + 1) % N을 이용해서 옮겨줘야 합니다.

정답 코드 https://github.com/Geniemo/BOJ/blob/master/15961.cpp

Categories:

Updated:

Leave a comment