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

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

15961번: 회전 초밥

1. 주의할 점

- 투 포인터를 이용하여 푼다. 매번 K개의 종류를 센다 -> TLE

 

2. 구현

- Arr[] 배열을 통해 연속된 K개의 초밥 중에 해당 종류의 초밥이 몇개 속해 있는지 나타낸다. Cnt를 통해 서로 다른 종류의 수를 나타낸다

- 벨트에 놓인 초밥의 종류를 Dish벡터에 담는다. 쿠폰을 사용하여 먹을 수 있는 초밥은 미리 표시한다. 동시에, 0~K-1번까지의 초밥에 대한 정보를 Arr에 담고, 새로운 종류가 추가될때마다 Cn++한다

- 벨트의 마지막 순서에서부터 연속된 K개만큼도 검사해야하기 때문에 Dish벡터뒤에 DIsh의 0~K번까지의 초밥을 추가한다

- While문을 수행하면서 연속된 K개의 초밥을 나타내는 시작부분을 L, 끝부분을 R이라고 할 때, L이 Num일 때 즉 한바퀴 전부 확인했을 때 종료한다

- 빠지는 초밥에 대해 Arr[]--, 추가되는 초밥에 대해 Arr[]++를 수행한다. --를 수행했을 때, Arr[]값이 0이면 Cnt--를 수행하고 ++를 수행했을 때, Arr[]값이 1이면 Cnt++를 수행한다

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> dish;
int arr[3001];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int num,kind,con,coupon,result=0,val;       //접시 수, 초밥 종류 수, 연속된 K, 쿠폰 번호, 결과 
    cin>>num>>kind>>con>>coupon;
    
    arr[coupon]=1;
    int cnt=1;      //가능한 종류 수
    int l=0,r=con-1;
    
    for(int i=0;i<num;i++){
        cin>>val;
        dish.push_back(val);
        if(i<con){
            arr[val]++;
            if(arr[val]==1) cnt++;
        }
    }
    for(int i=0;i<con;i++)
        dish.push_back(dish[i]);
    while(1){
        result = max(result,cnt);
        if(l==num) break;
        arr[dish[l]]--;
        if(arr[dish[l++]]==0) cnt--;
        arr[dish[++r]]++;
        if(arr[dish[r]]==1) cnt++;
    }
    cout<<result;
    return 0;
}

 

유사한 문제)

2020년 카카오?라인?에 출시되었던 보석의 개수 세는 문제와 유사하다