[백준 2531] 회전 초밥 (C++)

문제 링크: www.acmicpc.net/problem/2531

2531번: 회전 초밥

1. 주의할 점

- 두 포인터를 이용하여 문제를 해결한다

 

2. 구현

- 초밥에 대한 정보를 Arr[] 배열에 받는다

- rawFish[] 배열을 통해 특정 종류의 초밥의 수를 나타낸다

- Arr[]배열에서 0~K-1번에 해당하는 초밥을 rawFish[]에 더하며 rawFish[]의 값이 1이 되면 현재 초밥 종류의 수를 나타내는 Cnt에 1을 더한다

- 쿠폰으로 받는 C 초밥에 대해서도 위와 같은 식을 적용한다

- 두 포인터를 이용하여 Left =0, Right = K-1로 설정하여 Left가 Num이 될때까지 While문을 수행한다

- Result와 Cnt중 큰 값을 Result에 할당한다

- 현재 Left가 가리키는 초밥을 rawFish[]에서 1 뺀다. 이때, rawFish[]의 값이 0이 된다면 Cnt--한다. 이후, Left++를 수행한다

- Right++를 수행한다. 이때, Right가 Num이상의 값을 가질수 있으므로 Num으로 나눈 나머지를 Right에 할당한다

- 현재 Right가 가리키는 초밥을 rawFish[]에서 1만큼 더한다. 이때, rawFish[]의 값이 1이 된다면 Cnt++한다.

 

#include <iostream>
#include <algorithm>
using namespace std;
int arr[30000];
int rawFish[3001];
int num,d,k,c;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int result=0,cnt=0;
    cin>>num>>d>>k>>c;
    for(int i=0;i<num;i++)
        cin>>arr[i];
    int left=0,right=k-1;
    for(int i=0;i<k;i++){
        rawFish[arr[i]]++;
        if(rawFish[arr[i]]==1)
            cnt++;
    }
    rawFish[c]++;
    if(rawFish[c]==1) cnt++;
    
    while(left<num){
        result = max(result,cnt);
        if(--rawFish[arr[left++]]==0) cnt--;
        right = (right+1)%num;
        if(++rawFish[arr[right]]==1) cnt++;
        
    }
    cout<<result;
    return 0;
}