(JAVA) 백준 2531번 : 회전 초밥 -- [투포인터]

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

2531번: 회전 초밥

 

안녕하세요.

 

회전초밥ㅁ?ㅁ

투포인터를 사용하는 문제입니다.

하지만, start ~ end 길이가 고정된 길이기 때문에, sliding window 알고리즘이라고도 할 수 있겠죠.

 

위 그림이 회전초밥이라고 해서 마치 원형처럼 느껴져서 처음에 당황해하실 수 있는데요.

 

알고보면 간단합니다.

배열 길이(N개) 이상 넘어가면 해당 배열 길이만큼 % 연산을 수행하면 되니까요!

 

나머지는 문제에서 주어졌으니까 문제 없습니다.

 

중요한건!

연속해서 먹는 접시의 수와 쿠폰 번호 입니다.

 

연속해서 먹는 접시 = Sliding Window(길이는 K) 를 설정하고, 이를 한 칸씩 움직이면서 최대 먹을 수 있는 초밥의 종류를 얻으면 끝!

 

 

 

쿠폰 번호에 해당하는 초밥이 Window 안에 있다면?

-> count는 그대로!

 

쿠폰 번호에 해당하는 초밥이 Window 안에 없다면??

-> 오오! 초밥 한 종류 공짜로 하나 더 먹을수있네? 개이득! count + 1

 

해서 최대 초밥의 종류 개수를 얻으면 됩니다.

 

 

 

알고리즘

---

1. 스시 종류 번호 배열에 넣기

 

2. 초밥의 종류 개수(d) 크기의 배열 선언 -> 해당 배열은 index 번호의 초밥을 먹은 개수를 저장

 

3. 처음 0번부터 k개수만큼 먹었을 때를 파악해 값을 설정

  -> for(int i = 0; i < k; i++) 하면 쉽죠? 

  -> 이 초밥을 하나도 안먹었다면? count++

  -> 이 값이 현재 최대 초밥의 종류 개수 입니다.

 

4. 1번부터 n-1까지 for문으로 sliding window 수행

-> 1번부터 n-1번까지 start만 이동시키면 k는 고정이기 때문에 end를 활용할 필요가 없습니다.

-> end = (i + k - 1) % n 로 선언하고, 해당 지점에서 3번과 비슷하게 처리합니다. (코드참고)

-> start 지점 또한 end와 마찬가지로 3번과 비슷하게 처리합니다. (코드참고)

-> 현재 count값과 max값을 비교해서 max값을 갱신합니다. 이 때, 맨 위에 적은 것과 같이 쿠폰초밥을 먹었는지 안먹었는지 파악해서 개수파악을 잘 합니다.

 

 

이상입니다.

 

감사합니다.

 

소스코드

---