백준 2531번 회전 초밥 (C++)

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

2531번: 회전 초밥

문제 풀이는 다음과 같다. 

 

1. 문제에서 요구하는대로 변수들을 만들고 회전초밥의 값을 저장한다.

이때 회전초밥의 값을 저장할 배열의 사이즈를 2배로 하는 것이 포인트이다. (2배 말고도 n+k까지 세워도 상관은 없다.)

이유는 회전초밥이기 때문에 원형으로 이루어져있으며, 아래 그림과 같이 n번째에서 1번째, 2번째 ... 를 탐색할 필요가 있기 때문이다.

    int n,d,k,c,temp,ans=0;
    cin >> n >> d >> k >> c;
    vector<int> v(n*2+1);
    vector<bool> ch(d+1);
    for(int i=0; i<=d; i++) ch[i] = false;
    for(int i=1; i<=n; i++){
        cin >> temp;
        v[i] = temp;
        v[i+n]= temp;
    }  

 

2. 투 포인터 기법 중 '윈도우 슬라이싱'을 실행하기 위해 left, right, num(길이를 나타냄) 함수를 세운다.

편의상 1번 배열부터 값을 입력했으므로, right, left 모두 1로 설정하면 된다.

동시에 v[left]의 값은 이미 방문했다는 뜻으로 true로 표기해준다

    int left=1, right = 1, num = 1;
    ch[v[left]] = true;

참고로 윈도우 슬라이싱이란, 투 포인터와 기본 원리는 동일하나 움직이는 범위는 반드시 고정되어 있음을 뜻한다.

마치 창문을 왼쪽으로 오른쪽으로 움직이는 것과 동일해서 그렇게 이름이 붙여진 알고리즘이다.

 

3. 아래 코드를 천천히 봐보자.

    while(right<=n+k-1){ // 0
        right++; // 1
        ch[v[right]] = true;
        num++;
        if(num==k){ // 2
            temp = 0;
            for(int i=1; i<=d; i++) if(ch[i]) temp++;
            if(!ch[c]) temp++; // 3
            if(ans<temp) ans = temp; // 4 
            temp = 0; // 5
            for(int i=left+1; i<=right; i++){ // 6
                if(v[i]==v[left]) {temp++; break;}
            }
            if(temp==0) ch[v[left]] = false; // 7
            left++; // 8
            num--;
        }
    }

(0) 먼저 while문의 실행 조건은 right의 값이 n+k-1 이하일때 까지이다.

(1) right의 값을 +1 해주고, 동시에 ch[v[right]] = true로 바꾸어 해당 위치값을 방문했다고 표시해준다.

또한 지금까지 방문한 숫자의 길이를 +1해준다.

(2) 만약 이렇게 진행해서 방문한 숫자의 길이가 k일 경우, temp값을 0으로 초기화 해준 후 1번부터 초밥의 최대 번호인 d번까지 for문을 진행한다. ch[i]가 true일 경우, 해당 초밥을 집어먹었다는 의미로 temp를 +1 해준다.

(3) 만약 쿠폰번호와 동일한 번호의 초밥을 먹지 않았을 경우, temp를 +1해준다.

(4) 최대값을 갱신해준다.

(5) 다시 temp를 0으로 초기화해준다. 이제부터 할 것은 left의 값을 옮겨주는 과정인데, 이 부분이 중요하다.

(6) left+1번부터 right이하까지 for문을 돌리고, 만약 v[i]가 v[left]와 같을 경우, ch[v[left]]의 값을 해제(=false로 변경)할 수 없다.

예를 들어 지금까지 먹은 초밥의 번호가 7 -> 9 -> 7 -> 30일 경우, left값을 옮기기 위해 맨 왼쪽의 7번의 방문 여부를 해제하려해도 중간에 이미 7이 존재하기 때문에 해제가 불가능하다.

(7) temp의 값이 0일 경우 v[left]와 동일한 번호의 초밥이 없다는 의미이므로, ch[v[left]]를 false로 바꿔준다.

(8) left의 값을 +1 해주고 줄어든 길이를 고려하여 num을 -1해준다.

 

4. while문 종료 후 정답을 출력한다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n,d,k,c,temp,ans=0;
    cin >> n >> d >> k >> c;
    vector<int> v(n*2+1);
    vector<bool> ch(d+1);
    for(int i=0; i<=d; i++) ch[i] = false;
    for(int i=1; i<=n; i++){
        cin >> temp;
        v[i] = temp;
        v[i+n]= temp;
    }  
    int left=1, right = 1, num = 1;
    ch[v[left]] = true;
    while(right<=n+k-1){
        right++;
        ch[v[right]] = true;
        num++;
        if(num==k){
            temp = 0;
            for(int i=1; i<=d; i++) if(ch[i]) temp++;
            if(!ch[c]) temp++;
            if(ans<temp) ans = temp;
            temp = 0;
            for(int i=left+1; i<=right; i++){
                if(v[i]==v[left]) {temp++; break;}
            }
            if(temp==0) ch[v[left]] = false;
            left++;
            num--;
        }
    }
    cout << ans << "\n";
    return 0;
}

보다시피 여러번의 시도 후에 488ms -> 212ms로 시간을 반토박 이상 낸것까지는 좋았으나, 제출한 사람들을 보면 두 자리 단위수의 시간만 소비한 케이스도 있었다. 그런 분들은 어떻게 코드를 짠 것일지 궁금하다.