[백준] 회전 초밥

최근 코딩 테스트 트랜드로 투포인터 문제들도 간간히 보이는거 같아서 오랜만에 이런 유형의 문제를 풀어보았다. 처음 읽었을때는 되게 간단해 보여서 내가 그동안 연습했던 투포인터 형식으로 문제를 풀었지만 생각보다 잘 안됐고 좀 좌절 했다.

그런데 문제를 자세히 읽다보니 회전 초밥 배열을 N 만큼만 탐색 하는게 아닌 회전 하는 형식으로 만들어야 됐었다. 즉,

0 1 2 3 4 5 가 있다고 하고 연속되는 k의 숫자가 3 이라면은 5 0 1 까지도 탐색이 되야 한다는 소리였다.

보통 투포인터를 이용할때는 i와 j 인덱스를 애용하지만 이번에는 살짝 다르게 start 와 end 인덱스를 각각 같은 지점에서 시작하는게 아닌 k만큼 벌어진 구간에서 사용했다.

#include <iostream> 
#include <bits/stdc++.h> 
#define endl "\n"
#define MAX 100010
using namespace std;

int N, d, k, c; 
int matrix[3000001];
map<int,int> hashMap; 

void Input(){
    cin >> N >> d >> k >> c;
    for(int i = 0; i < N; i++){
        cin >> matrix[i]; 
    }
}

void Solution(){
    for(int i = 0; i < k-1; i++){
        hashMap[matrix[i]]++; 
    }
    int answer = 0, len = 0, start = 0, end = k-1; 
    for(int i = 0; i < N; i++){
        int curr = matrix[end%N]; 
        int move = matrix[start]; 
        hashMap[curr]++; 
        len = hashMap.size(); 
        if(!hashMap.count(c)) answer = max(answer,len+1); 
        else answer = max(answer,len); 

        if(--hashMap[move] == 0){
            hashMap.erase(move); 
        }


        start++;
        end++; 
    }

    cout << answer; 
}


void Solve(){
    Input();
    Solution(); 
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen("input.txt", "r", stdin);
    Solve();
    return 0;

}

앞으로도 투포인터 유형의 문제를 풀때 이런식으로 활용해봐야겠다.

배운점:
1. 투포인터 이론
2. 투포인터 변형