회전 초밥 (2531번) - 백준 (BOJ)

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

2531번: 회전 초밥

 

백준 - 회전 초밥 (2531번)

 

난이도 : Silver 1

알고리즘 : Simulation, deque

풀이 소요 시간 : 27분

 

import sys
input = sys.stdin.readline
from collections import deque, Counter


if __name__ == '__main__':
    N, d, k, c = map(int, input().split())
    _types = 0
    belt = [int(input()) for _ in range(N)]
    counter = Counter(belt[:k])
    dq = deque(belt[:k])
    
    for i in range(k, N+k):
        cur_types = len(counter)
        if c not in counter:  cur_types += 1
        _types = max(_types, cur_types)
        
        _out = dq.popleft()
        counter[_out] -= 1
        if not counter[_out]:
            counter.pop(_out)
        _in = belt[i%N]
        counter[_in] = counter.get(_in, 0) + 1
        dq.append(_in)
        
    print(_types)

 

최적화보다는, 모듈을 활용한 빠른 문제 해결에 초점을 두고 풀어봤다.

deque를 써서 한 칸씩 이동하는 기능을 구현하고,

Dictionary (Counter) 로 deque에 존재하는 서로 다른 초밥의 개수를 확인했다.