[BOJ 2531] 회전 초밥

https://www.acmicpc.net/problem/2531

2531번: 회전 초밥

문제 설명

연속된 k 개의 초밥을 먹으면 1개의 쿠폰을 준다.

이 때, 이벤트를 참여하면서 먹을 수 있는 초밥 개수의 최댓값을 구하자.

인사이트

처음에 생각한 방법

1. 투포인터를 사용하기 위해 deque을 사용하고 left, right를 이용해 슬라이딩 윈도우를 구현하자.
2. 한번의 슬라이딩 윈도우 탐색을 하고나면 deque의 원소를 unorderd_set 에 옮겨 중복되는 값을 제거하고 쿠폰으로 받는 초밥의 번호가 포함되어있는지 확인해 최대 가짓수를 최신화한다.

오류 코드

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

int N, d, k, c;

vector<int> rail;
unordered_set<int> s;
deque<int>dq;

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

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

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

    for (int i = 0; i < k; i++) {
        dq.push_back(rail[i]);
    }

    int left = 0;
    int right = k - 1;

    int maxx = dq.size();
    for (int i = 1; i <= N; i++) {
        dq.pop_front();

        left++;
        right++;

        if (left >= N) {
            left = 0;
        }
        if (right >= N) {
            right = 0;
        }

        dq.push_back(rail[right]);
        //최댓값 최신화

        unordered_set<int> tmp(dq.begin(), dq.end());

        bool is_coupon = false;

        if (tmp.find(c) != tmp.end()) {
            is_coupon = false;
        }
        else {
            is_coupon = true;
        }

        if (maxx <= tmp.size()) {
            maxx = tmp.size();
            if (is_coupon) {
                maxx += 1;
            }
        }
    }
    cout << maxx;
    return 0;
}

 

하지만 시간초과라는 결과를 얻게 되었다. for 루프를 돌 때마다 새로운 set을 생성하고 탐색하는 과정에서 O(Nk) 의 시간이 걸린다.

수정된 인사이트

1. deque 을 이용한 윈도우
   -> unordered_map 을 사용
2. unodered_set 을 사용한 중복제거
   -> unordered_map에서 key(초밥번호) 에 해당하는 value 값의 조정을 통해 중복이면 1 초과인지 확인을 해 체크

정답코드

#include <iostream>
#include <vector>
#include <deque>
#include <unordered_map>
using namespace std;

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N, d, k, c;
    cin >> N >> d >> k >> c;

    vector<int> rail(N);
    for (int i = 0; i < N; i++) {
        cin >> rail[i];
    }

    unordered_map<int, int> sushi_count;
    int total_types = 0; // 현재 윈도우 내의 초밥 종류 수
    int max_types = 0;

    // 초기 윈도우 설정
    for (int i = 0; i < k; i++) {
        if (sushi_count[rail[i]]++ == 0) total_types++;
    }
    // 쿠폰 초밥 추가
    if (sushi_count[c]++ == 0) total_types++;

    max_types = total_types;

    // 슬라이딩 윈도우
    for (int i = 1; i < N; i++) {
        // 앞에서 초밥 제거
        if (--sushi_count[rail[i-1]] == 0) total_types--;

        // 뒤에 새로운 초밥 추가
        int new_sushi = rail[(i + k - 1) % N];
        if (sushi_count[new_sushi]++ == 0) total_types++;

        // 쿠폰 초밥 확인
        max_types = max(max_types, total_types + (sushi_count[c] == 0));
    }

    cout << max_types;

    return 0;
}