[c++] BOJ 15961번 :: 회전초밥

 

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

내 코드

<첫번째 시도>

#include <iostream>
#include <algorithm>
#include <set>
#include <vector>

using namespace std;

int sushi_belt[3000000];
vector<set<int>> sushi_set;

int main() {
    int n, d, k, c;
    cin >> n >> d >> k >> c;
    for (int i = 0; i < n; i++)
        cin >> sushi_belt[i];

    /* 초밥 k개씩 끊어 읽기 */
    int index = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < k; j++) {
            sushi_set.push_back(set<int>());
            int tmp = (i + j > n - 1) ? i + j - n : i + j; // 원형 고려
            sushi_set[index].insert(sushi_belt[tmp]);
        }
        sushi_set[index++].insert(c);
    }

    /* 가짓수 가장 많은 것 읽기 */
    int max = 0;
    for (int i = 0; i < n; i++) {
        sushi_set[i].size() > max ? max = sushi_set[i].size() : max;
    }

    printf("%d", max);
}

set, vector를 이용해서 단순하게 구현

메모리초과

vector<set<int>> 이 메모리를 너무 잡아먹는 듯함 => k개씩 받아오는 순간 max를 계산하는 것으로 변경

<두번째 코드>

#include <iostream>
#include <set>

using namespace std;

int sushi_belt[3000000];

int main() {
    int n, d, k, c;
    scanf("%d %d %d %d", &n, &d, &k, &c);
    for (int i = 0; i < n; i++)
        scanf("%d", &sushi_belt[i]);

    /* 초밥 k개씩 끊어 읽기 */
    int max = 0;
    int skip_num;
    int skip = 0;
    for (int i = 0; i < n; i++) {
        set<int> sushi_set;
        skip_num = 0;
        skip = 0;
        for (int j = 0; j < k; j++) {
            if (skip_num >= k + 1 - max) {// 중복된 수가 max 경우보다 많아지면 바로 break
                // 제일 많이 나올 수 있는 종류의 수 k+1 - 이때껏 나온 최대 종류의 수 max
                skip = 1;
                break;
            }
            int tmp = (i + j > n - 1) ? i + j - n : i + j; // 원형 고려
            int compare_size = sushi_set.size();
            sushi_set.insert(sushi_belt[tmp]);
            if (sushi_set.size() == compare_size) { // 중복으로 들어오면
                skip_num++;
            }
        }
        if (skip)
            continue;
        sushi_set.insert(c);
        if(sushi_set.size() > max)
            max = sushi_set.size(); // 가짓 수 많은 걸로 max 채우기
    }

    printf("%d", max);
}

시간초과

중간에 skip 코드를 넣었는데도 시간초과 ..

시간 복잡도 최대로 계산해보니 9*10^9 이라 위험하긴 함! 하지만 줄일 방법을 모르겠음

<세번째 코드>

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int sushi_belt[3000000];
int sushi_kind[3001] = { 0 };

int main() {
    int n, d, k, c; 
    scanf("%d %d %d %d", &n, &d, &k, &c);
    for (int i = 0; i < n; i++)
        scanf("%d", &sushi_belt[i]);

    int index = 0;
    int kind = 0;
    queue<int> sushi_list;
    for (int i = 0; i < k; i++) {
        sushi_list.push(sushi_belt[i]);
        if (!sushi_kind[sushi_belt[i]]++) {
            kind++;
        }
    }
    int max = kind;

    /* 초밥 k개씩 끊어 읽기 */
    for (int i = k; i < n+k-1; i++) {
        if (!(--sushi_kind[sushi_list.front()])) {
            kind--;
        }
        sushi_list.pop();
        if (!sushi_kind[sushi_belt[i % n]]++) {
            kind++;
        }
        sushi_list.push(sushi_belt[i % n]);
        if (!sushi_kind[c]) {
            if (kind + 1 > max)
                max = kind + 1;
        }
        else {
            if (kind > max)
                max = kind;
        }
    }


    printf("%d", max);
}

정답!

슬라이딩 윈도우 방식으로 구현했어야 했다.

 

<주의>

 여기서 문제에서 잘 기재가 안되어있는 부분이 있는데 초밥의 종류인 d가 3이라고 하면 초밥은 1,2,3 이렇게 나온다(index가 1부터 시작). 그래서 sushi_kind라는 배열은 3001개로 만들어 주었다.

 기존에도 queue에 하나씩 넣고 빼면서 n번의 for문 한 번만 도는 방법은 생각해봤는데, 뽑은 k개의 초밥의 종류를 변수로 나타낼 수 있다는 생각을 못하고 k번의 for문을 안에서 돌아야된다고 생각해 복잡도가 비슷할 것으로 예상하여 구현하지 않았었다. 하지만 kind 변수를 이용하면 O(nk)에서 O(n)으로 시간복잡도를 줄일 수 있다.

=> 너무 쉽게 포기하고 답을 본 것 같아 민망하군..

 

<배운 것>

1. 슬라이딩 윈도우 방식

하나씩 빼고 넣고 하는 알고리즘에서는 슬라이딩 윈도우 방식을 사용하는 것이 편하다.

2. 원형을 구현하려면 그냥 모듈러 연산을 이용하면 된다.

n보다 큰 index에서의 경우도 고려하려면 index%n을 해주면 원형으로 구현할 수 있다.

3. 쿠폰을 준 c 초밥

c 초밥은 마지막에 삽입하면 다른 경우의 수를 계산할 때 다시 빼주어야하므로 그냥 kind 계산에만 고려하였다.