[백준] 회전 초밥 - 자바(Java)

문제 링크

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

문제 설명

회전 초밥 음식점에는 회전하는 벨트 위에 여러 가지 종류의 초밥이 접시에 담겨 놓여 있고, 손님은 이 중에서 자기가 좋아하는 초밥을 골라서 먹는다. 초밥의 종류를 번호로 표현할 때, 다음 그림은 회전 초밥 음식점의 벨트 상태의 예를 보여주고 있다. 벨트 위에는 같은 종류의 초밥이 둘 이상 있을 수 있다.

새로 문을 연 회전 초밥 음식점이 불경기로 영업이 어려워서, 다음과 같이 두 가지 행사를 통해서 매상을 올리고자 한다.

1. 원래 회전 초밥은 손님이 마음대로 초밥을 고르고, 먹은 초밥만큼 식대를 계산하지만, 벨트의 임의의 한 위치부터 k개의 접시를 연속해서 먹을 경우 할인된 정액 가격으로 제공한다.
2. 각 고객에게 초밥의 종류 하나가 쓰인 쿠폰을 발행하고, 1번 행사에 참가할 경우 이 쿠폰에 적혀진 종류의 초밥 하나를 추가로 무료로 제공한다. 만약 이 번호에 적혀진 초밥이 현재 벨트 위에 없을 경우, 요리사가 새로 만들어 손님에게 제공한다.

위 할인 행사에 참여하여 가능한 한 다양한 종류의 초밥을 먹으려고 한다. 위 그림의 예를 가지고 생각해보자. k=4이고, 30번 초밥을 쿠폰으로 받았다고 가정하자. 쿠폰을 고려하지 않으면 4가지 다른 초밥을 먹을 수 있는 경우는 (9,7,30,2), (30,2,7,9), (2,7,9,25) 세가지 경우가 있는데, 30번 초밥을 추가로 쿠폰으로 먹을 수 있으므로 (2,7,9,25)를 고르면 5가지 종류의 초밥을 먹을 수 있다.

회전 초밥 음식점의 벨트 상태, 메뉴에 있는 초밥의 가짓수, 연속해서 먹는 접시의 개수, 쿠폰 번호가 주어졌을 때, 손님이 먹을 수 있는 초밥 가짓수의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ k ≤ 3,000 (k ≤ N), 1 ≤ c ≤ d이다.

두 번째 줄부터 N개의 줄에는 벨트의 한 위치부터 시작하여 회전 방향을 따라갈 때 초밥의 종류를 나타내는 1 이상 d 이하의 정수가 각 줄마다 하나씩 주어진다.

출력

주어진 회전 초밥 벨트에서 먹을 수 있는 초밥의 가짓수의 최댓값을 하나의 정수로 출력한다.

입출력 예

입력	출력
8 30 4 30 7 9 7 30 2 7 9 25	5
8 50 4 7 2 7 9 25 7 9 7 30	4

문제 풀이

[고려사항]

단순하게 생각했을땐 벨트에 초밥이 올라가있는 순서를 따져서 N개 중 k개로 조합을 확인하면 될까 싶지만, 그렇게 하면 시간 초과가 된다. N은 최대 30,000개, k는 최대 3,000개인데, 모든 조합을 가져오면 O(N^k)이 걸리기 때문이다. 

[알고리즘, 구현방법]

이 문제는 고정된 범위(k)가 있고, 배열 순서대로 범위만큼씩 확인하는 것이 필요하므로 *슬라이딩 윈도우 알고리즘을 이용한다.

*슬라이딩 윈도우는 고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘이다.

 

✅ 1번째 정답

정답이긴 했으나, 다른 사람의 풀이를 확인했을때 내 코드에 비해 속도가 빨라서, 다른 방식으로 풀어야겠다고 생각했다.

[풀이 과정]

우선 List에 쿠폰 번호의 초밥을 넣고, k개의 초밥(0번 인덱스 ~ k-1번 인덱스)을 넣는다. 이러면 첫번째 윈도우(범위)의 초밥을 넣은것이 된다. 그 후 중복되는 초밥을 제외하고 수를 세기 위해 Set에 List를 그대로 넣고 Set의 size를 최대 초밥 종류수(maxCnt)에 할당한다.

• 7 9 7 30 2 7 9 25 가 벨트에 올라간 초밥이라면 현재 List에는 [30, 7, 9, 7, 30] 이 할당되어 있음

그리고 남은 경우를 확인할때는, (k-1)번만큼 반복하면서 모든 초밥 조합을 확인한다.

윈도우를 한칸씩 뒤로 밀면서 확인해야하므로, List의 1번 인덱스를 지우고 다음 초밥을 넣는다.

• 이때 List의 0번 인덱스에는 쿠폰 번호를 고정으로 넣어두었기에 1번 인덱스부터 k번 인덱스까지가 현재 확인하고 있는 벨트에 올라간 초밥이 된다. 
• '다음 초밥' 인덱스는 (반복문 인덱스 % N) 으로 설정한다. 회전 초밥이므로 배열의 끝까지만 탐색하면 되는것이 아니라, 윈도우(범위)가 마지막 인덱스에서 시작하면 맨 앞 초밥도 해당 경우의 수에 포함되어야 하기 때문이다
  • 7 9 7 30 2 7 9 25 로 초밥이 배치된 벨트에서, 25가 윈도우의 시작이면 현재 윈도우는 25,7,9,7(7 9 7 30 2 7 9 25)이기 때문

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        int d = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());

        int[] sushi = new int[N];
        for (int i=0; i<N; i++) {
            sushi[i] = Integer.parseInt(br.readLine());
        }
        List<Integer> list = new ArrayList<>();
        list.add(c); // 쿠폰 번호는 고정으로 추가
        for (int i=0; i<k; i++) {
            list.add(sushi[i]);
        }
        Set<Integer> set = new HashSet<>(list);
        int maxCnt = set.size(); // 최대 종류 수

        for (int i=k; i<N+k; i++) {
            list.remove(1);
            list.add(sushi[i % N]);

            set = new HashSet<>(list);
            if (maxCnt < set.size()) {
                maxCnt = set.size();
            }
        }
        System.out.println(maxCnt);
    }
}

✅ 2번째 정답 (속도 개선)

결론부터 말하면 속도를 2,840ms에서 168ms로 (2,672ms)개선했다.

 

첫번째 시도에서는 List, Set을 이용해서 문제를 풀었는데, 두번째 풀이방식에서는 초밥을 카운팅하는 배열을 생성해서 풀어서 속도를 개선할 수 있었다. 

첫번째 시도에서는 List에 k개의 요소를 추가하고 제거하는데에 O(k) 만큼 소요되고, List를 Set으로 변환하는데에도 O(k)가 소요된다. 이 과정을 윈도우가 한칸씩 옮겨질때마다 수행하므로 총 O(N*k) 만큼 소요된다. 

두번째 시도에서는 윈도우를 이동할 때 List, Set을 생성하거나 변환하지 않고 단순히 배열의 값을 갱신하는 방식이기에 O(N)만큼만 걸려서 훨씬 효율적으로 문제를 풀 수 있는 것이다.

[풀이 과정]

윈도우에 포함되는 초밥의 종류별로 카운팅하기 위한 배열(sushi)과 벨트 위에 있는 초밥을 저장하기 위한 배열(plates)을 생성해서 이 두 배열을 가지고 문제를 풀었다. 

 

첫번째 윈도우를 세팅할 때, 윈도우 내에 있는 초밥의 카운팅을 1씩 추가한다. 이때, 초밥의 종류 수는 새로운 초밥인 경우에만 플러스한다.

그리고 N번만큼 반복하며 모든 초밥 조합을 확인한다.

반복문을 돌기 전에 이미 첫번째 윈도우는 세팅되어있기 때문에 반복문 상단에서 초밥 종류의 최대 가짓수를 계산한다.

• 이때 쿠폰 번호의 초밥이 윈도우 내에 포함되어있지 않다면(=초밥 종류별 카운팅이 0이라면) 초밥 종류 가짓수를 1 더해서 계산한다.

이후에 윈도우를 한칸씩 이동하면서 초밥의 종류수를 계산한다. 이때 아래 두 조건을 고려하여 구현한다.

• 윈도우 내의 첫번째 초밥을 제외할 때 윈도우내에 중복된 초밥이 있었다면 종류 수를 빼면 안된다.
• 다음 초밥 가져올때는 중복된 초밥이라면 카운팅을 하면 안된다. 즉, 새로운 종류인 경우에만 카운팅해야한다.

모든 초밥의 조합을 확인한 후 초밥의 최대 종류 수를 출력하면 된다.

 

정답 코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        int d = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());

        int[] sushi = new int[d+1]; // 초밥 모든 종류의 카운팅을 위한 배열
        int[] plates = new int[N]; // 벨트 위 접시에 있는 초밥
        for (int i=0; i<N; i++) {
            plates[i] = Integer.parseInt(br.readLine());
        }

        // 첫번째 윈도우 세팅
        // 첫번째 초밥부터 k번째 초밥까지 윈도우(범위)로 설정
        int cnt = 0; // 현재 윈도우의 종류 수
        for (int i=0; i<k; i++) {
            sushi[plates[i]]++; // 윈도우 내에 있는 초밥 카운트 up
            if (sushi[plates[i]] == 1) cnt++; // 새로운 초밥 종류인 경우에만 카운팅
        }

        int max = 0; // 최대 종류 수
        for (int i=0; i<N; i++) {
            if (sushi[c] == 0) max = Math.max(cnt+1, max); // 현 윈도우에 쿠폰 초밥이 없는 경우
            else max = Math.max(cnt, max);

            // 윈도우(범위) 이동
            // 첫번째 초밥을 제외할 때, 윈도우내에 중복된 초밥이 있었다면 종류 수를 빼면 안됨
            if (--sushi[plates[i]] == 0) cnt--;

            // 다음 초밥 가져올때, 중복된 초밥이라면 카운팅을 하면 안됨. 새로운 종류인 경우에만 카운팅
            if (sushi[plates[k++ % N]]++ == 0) cnt++;
        }
        System.out.println(max);
    }
}