BOJ 백준 15961 : 회전 초밥

시작하면서

이번 문제는 투 포인터(Two Pointer) 카테고리 문제이다.

BOJ 15961 - 투 포인터

​

문제 이해

​ 이 문제는 회전 초밥임을 보면 순환되는 연결리스트가 떠오른다. 가장 앞과 뒤가 연결되어 있고, 중간 값이 아닌 가장 앞과 뒤가 삭제/추가되는 문제이므로 앞/뒤를 빼고 더해가면서 조건을 확인하면 문제가 해결된다.

​

해결

#include <iostream>
#include <vector>
#include <utility>

using namespace std;

int main()
{
    // sync off
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // sync off
    
    int N, d, k, c;

    cin >> N >> d >> k >> c;

    vector<int> plates(N);
    for (int i = 0; i < N; i++)
    {
        cin >> plates[i];
    }

    vector<int> sushiCounts(d + 1);
    int nonDuplicatedSushiCount = 0;
    int currentIndex = 0;

    // 1. 최초 초밥 k 그릇 만큼 초기화
    for (int i = 0; i < k; i++)
    {
        if (sushiCounts[plates[i]] == 0)
        {
            nonDuplicatedSushiCount++;
        }
        sushiCounts[plates[i]]++;
    }
    currentIndex++;

    // 2. 나머지 인덱스 반복
    int maxNonDuplicatedSushiCount = nonDuplicatedSushiCount;
    while (currentIndex != N)
    {
        // 3. 이전 1그릇 제거
        sushiCounts[plates[currentIndex - 1]]--;
        if (sushiCounts[plates[currentIndex - 1]] == 0)
        {
            nonDuplicatedSushiCount--;
        }

        // 4. 뒤 1그릇 추가
        int newPlateIndex = currentIndex + k - 1;
        newPlateIndex = (newPlateIndex >= N) ? (newPlateIndex - N) : newPlateIndex;
        if (sushiCounts[plates[newPlateIndex]] == 0)
        {
            nonDuplicatedSushiCount++;
        }
        sushiCounts[plates[newPlateIndex]]++;

        // 5. 쿠폰 초밥과 겹치는 초밥이 있는지 검사
        int nonDuplicatedSushiCountWithCoupon = nonDuplicatedSushiCount;
        if (sushiCounts[c] == 0)
        {
            nonDuplicatedSushiCountWithCoupon++;
        }

        // 6. 최대값 갱신
        maxNonDuplicatedSushiCount = max(maxNonDuplicatedSushiCount, nonDuplicatedSushiCountWithCoupon);
        currentIndex++;
    }

    cout << maxNonDuplicatedSushiCount;

    return 0;
}