[C++] 백준 15961 - 회전초밥

문제 이해 단계

---

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

15961번: 회전 초밥

 

회전 초밥의 개수 N, 회전 초밥의 종류 d,
연속해서 먹을 수 있는 개수 k, 쿠폰 번호 c가 들어온다.

여기서 회전 초밥은 원형으로 시계 방향으로 돌아가는데,
종류가 d개만큼 있다는 것을 의미한다.


시계 방향으로 돌아가는 회전 초밥을 연속해서 k개 먹을 때,
최대한 많은 종류를 먹는 것이 목표이다.

이때, 먹은 k개의 종류 중 쿠폰 번호에 해당하는 초밥이 없다면,
쿠폰 번호에 해당하는 종류를 먹을 수 있다.

이 조건일 때, 최대한 많은 종류의 초밥을 먹을 때, 그 개수를 구하는 문제.

 

 

문제 접근 단계

---

회전 초밥 N개 중 연속한 k개의 초밥 종류를 확인해야 하는 것은 알겠다.
그런데 문제는 N과 k의 범위이다. 

N의 범위는  최대 3,000,000이고, k의 범위는 3,000이다.
최악의 경우 3*10^9으로 제한시간인 1초가 넘어가 시간초과가 발생한다.

 

덱을 이용하여 탐색

그래서 자료구조 중 덱을 사용하여 배열을 한번 훑는 것으로 끝내기로 했다.
연속하는 k개를 파악하는 것이기 때문에 덱을 이용하면 쉽게 가능하다.

먼저 k개를 넣어두고 가장 앞에 있는 초밥을 빼고,
새로운 초밥을 넣음으로써 연속성을 유지할 수 있다.

그 과정에서 덱 안에 있는 k개의 초밥의 종류를 확인함으로써
총 몇 가지 종류인지를 확인할 수 있다.

 

 

초밥 종류 중복 확인

 

덱 안에 들어있는 초밥 종류의 중복을 어떻게 확인할까?
매번 덱 안에 있는 원소들을 다 빼서 비교해야 하나?
그럼 또 시간초과가 뜰 것이다.

 

사용한 방법은 초밥 종류의 개수를 세어주는 배열 변수를 만들어주는 것이다.
각 초밥이 현재 덱에 존재하는지,
존재한다면 몇 개가 있는지 저장해 둠으로써 종류의 개수를 구할 수 있다.

 

예를 들어, sushi [4] = 1이라는 것은,
현재 덱 안에 4라는 초밥 종류가 1개 존재한다는 소리이다.


반대로, sushi [10] = 0 이란 뜻은,
현재 덱 안에 10이란 초밥이 존재하지 않는단 뜻이다.

 

해당 방식을 사용하여, 덱 가장 앞에 있는 초밥을 빼면서,
새로운 초밥을 넣어줄 때 종류의 개수를 갱신할 수 있다.


덱 가장 앞에 있는 초밥을 빼면서 sushi [해당 초밥의 종류] - 1을 한다.

 

그 후 덱을 체크했을 때 sushi [해당 초밥의 종류] = 0이라면,
더 이상 그 종류는 없는 것이므로 종류가 하나 줄어든 것이다.


반대로, 새로운 초밥을 넣기 전에 덱 안에 sushi [새로운 초밥] = 0이라면,
덱 안에 새로운 종류의 초밥이 추가되는 것이다.

 

이런 식으로 할 수 있다. 자세한 것은 문제 구현 단계에서 다루겠다.
이제 문제 구현 단계로 가보자.

 

 

문제 구현 단계

---

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int sushi[3001] = {0}; // 초밥 종류
int main(){
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    int N,d,k,c;
    cin >> N >> d >> k >> c;
    vector<int> dish(N); // 초밥 개수
    for(int i = 0; i < N; i++) cin >> dish[i];

    deque<int> dq;
    int result = 0; // 결과
    int cnt = 0;
    // 일단 덱에 k개 만큼 넣기
    for(int i = 0; i < k; i++){
        int val = 0;
        dq.push_back(dish[i]);
        // 새로운 초밥 종류일때
        if(!sushi[dish[i]]){
            cnt++; // 개수+1
        }
        sushi[dish[i]]++;
    }
    result = cnt;

    for(int i = 0; i < dish.size(); i++)
    {
        int del = dq.front(); // 가장 앞에 있는 뺄거
        dq.pop_front();
        sushi[del]--; // 빼줌
        if(!sushi[del]) cnt--; // 안에 더이상 없으면 삭제

        dq.push_back(dish[(i+k)%N]); // 원형이니까 처음으로 돌아감
        if(!sushi[dish[(i+k)%N]]) cnt++; // 새로운 초밥이면 종류+1
        sushi[dish[(i+k)%N]]++;

        // 덱에 쿠폰에 해당하는 초밥이 없을 때
        if(!sushi[c]) {
            result = max(result,cnt+1);
        }
        // 덱에 쿠폰에 해당하는 초밥이 있을 때
        else result = max(result,cnt);
    }
    cout << result;
}

핵심적인 코드는 아래에 있는 for문 두 개다.

먼저 덱에 k개만큼 초밥을 넣는다.
초밥을 넣을 때 초밥 종류와 종류의 개수에 해당하는 cnt를 갱신한다.

이후 초밥의 개수만큼 탐색을 시작한다.
이때 k가 더해지는 이유는 이미 0~(k-1) 초밥은 탐색을 해서 덱에 넣어줬다.

그래서 k번째 초밥부터 해주기 위해서이다.
또한 원형배치이기 때문에 마지막 인덱스 다음에 처음으로 돌아와야 한다.
그래서 (i+k)% N을 해주는 것이다.

덱 가장 앞에 있는 것을 빼주고 새로운 초밥을 뒤에서 넣어준다.
그리고 초밥 중복을 확인해 준다. 

마지막으로 쿠폰에 해당하는 초밥 종류가 포함되어 있는지
확인하여 없다면 cnt+1 하여 준다.

이런 식으로 탐색을 진행하여 가장 큰 값이 result인 답이 된다.

 

시행착오

---

두 포인터 문제를 처음 풀어봤다.
말만 많이 들어봤지 직접 풀어보는 것은 처음이다.

덱을 이용해서 풀어볼까도 했는데,
생각보다 쉽지 않네. 이 문제 못 풀어서 아쉽다.

인터넷을 참고할 때, 초밥 종류의 개수를 조절하는 부분이 어려웠다.
그래도 투포인터 문제를 풀어봐서 어떤 건지는 알겠다.