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

2531번: 회전 초밥

완전 탐색을 통해 결과를 구한 문제이다. 문제 유형은 두 포인터로 되어 있는데 사실 슬라이딩 윈도우에 더 가까운 문제이다. 처음에는 중복 제거를 위해 set을 통해 원소들을 저장해 최대 크기를 구하는 방식으로 알고리즘을 구현했었는데 시간 초과가 났었ek... 이유는 set의 insert의 시간복잡도가 O(logN) 이었기 때문이었다. 이 부분은 기억을 해두어야겠다. 그래서 check배열을 통해 중복 검사를 해주면서 카운트를 해서 최댓값을 구해주었다. set에 대해 더 알 수 있었던 문제였다.

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int N, d, k, c;
vector<int> v;
bool check[3001];

void solution() {
    int result = 0;

    for (int i = 0; i < N; i++) {
        int count = 0;

        for (int j = i; j < i + k; j++) {
            if (!check[v[j % N]]) {
                check[v[j % N]] = true;
                count++;
            }
        }

        if (!check[c]) count++;

        result = max(result, count);
        memset(check, false, sizeof(check));
    }

    cout << result;
}

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

    cin >> N >> d >> k >> c;

    int a;
    for (int i = 0; i < N; i++) {
        cin >> a;
        v.push_back(a);
    }

    solution();

    return 0;
}