회전 초밥 (feat. 백준, 15961번)

회전 초밥
https://www.acmicpc.net/problem/15961

15961번: 회전 초밥

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
int arr[3000000], N, D, K, C, check[3001];
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    cin >> N >> D >> K >> C;
    memset(check, 0, sizeof(check));
    for(register int n = 0; n < N; ++n)
        cin >> arr[n];
    register int s = 0, ans = 0, cnt = 0;
    for (register int i = 0; i < K; i++) {
        if(check[arr[i]] == 0)
            ++cnt;
        ++check[arr[i]];
	}
    while (s < N) {
        if(check[C] == 0)
            ans = max(ans, cnt + 1);
        else
            ans = max(ans, cnt);
        // S + K의 위치 검사
        if(++check[arr[(s + K) % N]] == 1)
            ++cnt;
        // S의 위치 검사
        if(--check[arr[s]] == 0)
            --cnt;
        ++s;
	}
    cout << ans;
    return 0;
}
// *&)*@*

 

반응형

1. K개가 윈도우가 되어 S부터 한칸씩 옆으로 이동되는 모양이라고 생각해보면 쉽습니다.
2. 처음 K개만큼 마킹을 해둔 뒤, 한칸씩 옆으로 이동된다면, S 위치는 빼주고 K+1의 위치는 더해주면서 마킹된 정보로 총 개수를 구하면 됩니다.
3. 최초에는 자료구조 set을 이용하였으나 시간초과 판정을 받아 카운트마스킹 (비트마스킹처럼) 형태로 풀어보았습니다.