[Java] 백준 15961번 - 회전 초밥

• 문제
  • 링크 : https://www.acmicpc.net/problem/15961
  • 손님이 먹을 수 있는 초밥 가짓수의 최댓값

 

• 조건
  • 초밥은 한 방향으로 회전
  • 같은 종류의 초밥이 있을 수 있음

 

• 입력
  • 첫번째 줄
    • N : 회전 초밥 벨트에 놓인 접시의 수(2 ≤ N ≤ 3,000,000)
    • d : 초밥의 가짓수(2≤d≤3,000)
    • k : 연속해서 먹는 접시의 수(2≤k≤3,000, k≤N)
    • c : 쿠폰 번호(1 ≤ c ≤ d)
  • 두번째 줄부터~
    •  초밥의 종류
    • 1 ~ d 사이의 정수

 

• 출력
  • 손님이 먹을 수 있는 초밥 가짓수의 최댓값

 

• 로직 1)

import java.util.*;
import java.util.stream.Collectors;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt(); // 접시의 수
        int d = sc.nextInt(); // 초밥의 가짓수
        int k = sc.nextInt(); // 연속해서 먹는 접시의 수
        int c = sc.nextInt(); // 쿠폰 번호

        int answer = 0; // 손님이 먹을 수 있는 초밥의 최대 가짓수

        List<Integer> couponIndex = new ArrayList<>();
        int[] sushi = new int[N];
        for(int i=0; i<N; i++) {
            sushi[i] = sc.nextInt();
            if(sushi[i] == c) couponIndex.add(i);
        }
        couponIndex = couponIndex.stream()
                .sorted()
                .collect(Collectors.toList());

        int count = 0;
        while(count < N) {
            int tmp = 1;
            boolean b = sushi[count%N] == c ? false : true;
            for(int i=1; i<k; i++) {
                int index = (count+i)%N;
                if(sushi[index] == c) b = false; // 쿠폰 번호가 있는 경우
                if(sushi[index] != sushi[(count+i-1)%N]) tmp++;
            }

            if(answer < tmp) answer = tmp;
            if(tmp == k && b) {
                answer = k+1;
                break;
            }
            count++;
        }

        System.out.println(answer);
    }
}

 

• 결과
  • 틀렸습니다.
  • 해결방법 : 슬라이딩 윈도우 & 투포인터 알고리즘 사용하기