백준 15961, 2531. 회전 초밥

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

15961번: 회전 초밥

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

2531번: 회전 초밥

 

두 문제가 같은 문젠데, 접시의 수 n의 최댓값만 3만과 3백만으로 다르다. 

어처피 문제는 O(n) 시간복잡도로 풀리기 때문에 푸는 방법은 같다.

 

우선 초밥들은 원형으로 배치되어 있다. 초밥이 다음과 같이 주어지면 

 

7 9 7 30 2 7 9 25 

 

맨 뒤의 25뒤에 다시 7, 그다음 9 .. 이렇게 반복되는 구조다.

 

이렇게 원형으로 값들이 주어지면 i의 원소를 i+n에 추가해주면 탐색이 쉬워진다.

 

7 9 7 30 2 7 9 25 7 9 7 30 2 7 9 25 

 

배열을 이렇게 만들어주면 기존에 주어진 배열의 끝에 도달했을때 자연스럽게 다음은 첫 원소를 탐색할수 있게 된다.

 

이렇게 배열을 만든 후에는 처음 k개의 초밥의 합을 구하고, 왼쪽 초밥을 빼고 오른쪽 초밥을 추가하는 방식으로 계산하면 O(N) 시간복잡도로 모든 연속된 k개의 초밥을 먹었을 경우를 계산할수 있다.

 

k개의 초밥들이 선택됐을때 몇가지인지를 판단하는 방법은 초밥의 가짓수가 최대 3천개이므로 3천 크기의 int형 배열 mark를 만들고,

왼쪽 초밥을 뺀 후에, mark[왼쪽초밥 값]이 0이 된다면 왼쪽 초밥은 더 이상 내가 선택한 k개의 초밥중에 없으므로 종류 카운트를 1감소 시키고,

 

오른쪽 초밥을 추가하기 전에, mark[오른쪽초밥 값]이 0이였다면 이번에 선택한 오른쪽 초밥이 방금까지 내가 선택한 k개의 초밥중에 없었었고 이제 추가되었으므로 종류의 카운트를 1증가 시키면된다.