백준 2531. 회전 초밥 (투포인터)

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

2531번: 회전 초밥

연속된 수열을 구하는 문제이므로 투포인터 사용

 

 

1. 삽질 포인트

1. 문제 이해 관련 -> "연속해서 먹는 접시의 수 k를 다채워야 쿠폰 c가 생김" 간과함.

그래서 겹치는 값이 없는 최대 수열을 찾음-> c값이 있으면 + 1 하는 코드를 작성.

 

2. 투포인터 관련 (st, en = 0 으로 시작)

2-1) en < st 가 되는 경우가 있을 수 있음. en을 증가시킬때 en이 n-1보다 커지면 en을 starting point인 0으로 바꿔주야함

2-2) 겹치는 값 관리

-> 값이 들어오면 isvis[arr[en]] += 1

-> st가 다음 값을 가리키면 isvis[arr[st]] -= 1

2-3) 수열에 c가 있는지 관리

-> c 값이 들어오면 isvis[c] += 1 그리고 현재 수열에 c 있음으로 표시

-> arr[st] == c 이고 isvis[c] == 1(현재 st가 가리키는 값이 수열의 마지막 c값이면): 현재 수열에 c 없음으로 표시

2-4) st값이 바뀔때, 관련 변수 처리

-> 현재 arr[st]값이 빠짐에 따라 연속해서 먹는 접시 수(count), 초밥 종류의 개수(num), 수열에 들어있는 초밥의 종류별 개수(isvis)가 달라짐

 

2. 특징

1) 기본적인 투포인터 

2) st값이 바뀌기 전에, 관련 변수들을 빼먹지 않고 처리해줘야한다.

 

3. 코드

#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <tuple>
#include <set>
#include <cstring>
#include <string>
#include <stdio.h>
#include <limits.h>
//#include <bits/stdc++.h>
using namespace std;

int n, d, k, c;
int arr[30002];
int isvis[3002]; // 수열에 들어있는 초밥의 종류별 개수
int main() {
    
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> d>> k >> c;

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

    int en = 0; 
    //while문을 보면 en이 1부터 시작하기 때문에 en가 0일때 처리를 해주고 시작함(ex. count, num, isvis[arr[0]]을 1로 설정)
    int count = 1; // 연속해서 먹는 접시 수 
    int num = 1; //현재 수열에 들어있는 다른 종류의 초밥 수
    bool isC = false; //c종류 초밥이 있는지 체크
    int mx = 0; // 초밥 가짓수의 최댓값
    isvis[arr[0]] += 1;
    for(int st = 0; st < n; st++)
    {   
        while(count < k) 
        {
            count++;
            en++;
            if(en == n) {en = 0;}
            if(isvis[arr[en]] == 0) {num++;} // 수열에 해당 종류의 초밥이 없으면
            if(arr[en] == c) {isC = true;} // 해당 종류 초밥이 c이면 
            isvis[arr[en]] += 1; 
            
        }

        if(isC)
        {
            mx = max(mx, num);
        }
        else
        {
            mx = max(mx, num + 1);
        }

        //st 다음 값으로 옮기기 전 처리
        if(arr[st] == c && isvis[arr[st]] == 1) 
        {
            isC = false;
        }

        if(isvis[arr[st]] == 1)
        {
            num -= 1;
        }

        isvis[arr[st]] -= 1; 
        count -= 1;
        
    }

    cout << mx;

 
}