[ 백준 2531 ] 회전 초밥 (C++) - 투 포인터

---

🔗 문제 링크

2531번: 회전 초밥

---

💡 문제 풀이 및 해석

일단, 브루트포스로 할시 3000 * 30000으로 9천만 번의 실행을 해야 하는데, 이론상 1초 안에 가능하지만, 실제 해보니 시간초과가 났다. (아마, 메서드를 불러오고 입출력에서 시간을 쓰이는 것 같다.)

1. 브루트포스하게 해결할 수 없다. 따라서 다른 방법을 생각해야한다.
2. '연속'하는 회전초밥을 먹었고, 추가적으로 한 접시를 더 주는 조건이 이미 있다.
3. 매번 연속하는 것이고, 한 칸씩 밀면서 진행가능하므로 시작과 끝을 지정하는 투 포인터로 풀 수 있다.
4. D라는 배열에 현재 초밥종류를 넣고, 이미 있다면, 종류에 추가해주지 않는다.
5. 매번 시작 지점의 종류를 D의 상태에 따라 더해주고, 빼주면서 start 지점을 1~N까지 반복해 준다.

---

⭐️ 정답 코드 및 설명

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

int N, d, k, c;
int D[3001];
vector<int> table;
void input() {
    cin >> N >> d >> k >> c;
    table = vector<int>(N);
    for (int i = 0; i < N; i++) {
        cin >> table[i];
    }
}

int sol() {
    int answer = 0;
    int temp = 0;

    for (int i = 0; i < k; i++) {
        if (D[table[i]] == 0) {
            temp++;
            D[table[i]]++;
        }
        else {
            D[table[i]]++;
        }
    }
    if (D[c] == 0) {
        answer = temp + 1;
    }
    else {
        answer = temp;
    }


    for (int i = 1; i < N; i++) {
        int next = (i + k - 1) % (N);
        int post = i - 1;
        /*cout << post + 1<< " : " << next << endl;*/
        //cout << table[post + 1] << " : " << table[next] << endl;
        if (D[table[post]] > 1) {
            D[table[post]]--;
        }
        else {
            D[table[post]]--;
            temp--;
        }
        if (D[table[next]] == 0) {
            temp++;
            D[table[next]]++;
        }
        else {
            D[table[next]]++;
        }
        if (D[c] == 0) {
            answer = max(answer, temp + 1);
        }
        else {
            answer = max(answer, temp);
        }
        //cout << answer << endl;
    }

    return answer;
}

int main() {
    ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);

    input();
    cout << sol();

    return 0;
}

---

🤔 문제 후기

아직 Set을 활용한 브루트포스한 방식이 왜 안되는지 이해가 되지는 않지만, 더 빠른 투 포인터 방식을 알았으니 크게 신경 쓰지 않았다. 사실 투 포인터 방식으로 풀게 된 문제였다면, 브루트포스하게 접근도 못하게 시간을 줄였어도 좋았을 것 같은 문제였다.