[백준] 2531 회전초밥

백준: 문제

2531번: 회전 초밥

평소 투 포인터, 슬라이딩 윈도우 알고리즘 문제를 많이 풀어보지 않아서 직접 찾아서 풀어보았다. 기본적으로 너비가 고정된 투포인터가 슬라이딩 윈도우 문제이기 때문에 포인터를 2개로 잡아도 되고, 1개로 잡아도 된다. 하지만 2개로 잡으면 그만큼 신경 쓸 게 많아지기 때문에 여기서는 구간의 오른쪽 끝 포인터만 잡고, 나머지 하나는 그 포인터에서 주어진 너비를 감소함으로써 왼쪽 끝 포인터로 설정하였다.

회전

무엇보다 이 문제는 제목 그대로 '회전'을 해야하는 문제이므로 인덱스 처리가 중요했다. 이를 위해서 mod (%)를 이용해 배열의 인덱스 처리를 해주었다. 그리고 반복문의 조건을 편리하게 잡기 위해 미리 윈도우를 접시 조합의 마지막 경우로 채우고 시작하고 for문으로 추가해야하는 접시를 탐색시에는 앞에서부터 진행한다.

문제 이해

처음에는 쿠폰으로 주어지는 초밥도 연속하는 k 접시에 인접해야하는 줄 알았으나, 그게 아녔다.. 여기서 된통 깨졌다. 매번 문제 이해를 잘못 해서 시간을 많이 날리게 된다.. 어차피 문제에서 최종적으로 요구하는 것은 최대 초밥 종류이므로 k 배열 내에 쿠폰에 쓰인 초밥이 없으면 하나 추가하고, 있으면 STAY해주면 된다.

 

#include <iostream>
#include <algorithm>

using namespace std;

int arr[30001] = {0};
int kind[3001] = {0};

int main(void){
    int N, d, k, c;
    int sum = 0, mx = 0;
    cin >> N >> d >> k >> c;
    for(int i = 0;i < N;i++){
        cin >> arr[i];
    }
    // 윈도우를 뒤에서 채우고 시작(맨 앞부터 채우면 뒤의 for문 종료조건 잡기 어려움)
    for(int i = N - k;i < N;i++){
        if(kind[arr[i]] == 0) sum++;
        kind[arr[i]]++;
    }
    // 윈도우 끝점
    for(int i = 0;i  <N;i++){
        // 현재 윈도우에 없는 값으로 종류++
        if(kind[arr[i]] == 0) sum++;
        kind[arr[i]]++;
        // 지워야하는 접시의 인덱스
        int del = (i + N - k) % N;
        if(kind[arr[del]] == 1) sum--;
        kind[arr[del]]--;
        // kind[c] != 0이면 sum에 차이가 없다
        mx = max(mx, sum + (kind[c] == 0));
    }
    cout << mx;
}