[C++/백준] 2531번: 회전 초밥

문제 링크

2531번: 회전 초밥

 

풀이

투 포인터 문제
보통 이런 종류 문제는 set을 먼저 생각하게 되는데, 이렇게 크지 않은 숫자로 있다면 그냥 배열로(index) 체크하는 게 나을 듯 함

1. 0번째 인덱스부터 k개의 스시 종류를 체크해둔다.
   1. 초밥은 1번부터 d번까지 있기 때문에, 각 인덱스에 해당 인덱스 스시가 몇 개 들어가있는지 있게 된다.
   2. check 함수는 그 스시 배열에서 쿠폰을 사용할 무료 스시는 빼고 가짓수를 체크하게 된다.
2. 이제 1번째 스시부터 하나씩 k개를 체크해보는데, 1번에서 구했던 종류에서 앞에 하나 빼고 뒤에 하나 추가하는 식으로 sushi 배열을 갱신하고 check한다.
3. 이 때 인덱스를 넘어갈 경우, 해당 벨트는 원형 배열? 이기 때문에 인덱스 계산을 통해 앞의 인덱스를 구해준다.

 

코드

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

int check(vector<int>& sushi, int c)
{
    int cnt = 0;
    for (int i = 0; i < sushi.size(); i++)
    {
        // 무료 스시는 빼고 가짓수 체크
        if (sushi[i] > 0 && i != c) cnt++;
    }
    return cnt;
}

int main()
{
    int n, d, k, c;
    cin >> n >> d >> k >> c;

    vector<int> belt(n);
    vector<int> sushi(d + 1, 0); // 스시 종류 체크

    for (int i = 0; i < n; i++)
    {
        cin >> belt[i];
    }

    for (int i = 0; i < k; i++)
    {
        sushi[belt[i]]++;
    }

    int answer = check(sushi, c);

    for (int i = 1; i < n; i++)
    {
        if (i + k - 1 < n) sushi[belt[i + k - 1]]++;
        else sushi[belt[i + k - 1 - n]]++;
        sushi[belt[i - 1]]--;
        answer = max(answer, check(sushi, c));
    }
    cout << answer + 1;
}