[백준 2531번] 회전초밥 파이썬

회전초밥

종류: 브루트포스

문제 출처: 회전초밥

🍤 알고리즘
#1) 접시 수 만큼 연속된 d개의 조합을 구한다. (중복되는 수가 담기지 않도록 set사용)
#2) 쿠폰번호 추가
#3) 최대 길이 수 출력

N: 접시수, d: 초밥 가지수,k: 연속해서 먹을 수 있는 초밥 수, 쿠폰번호:c

알게된 점
원형이라 연속되어야 함으로 코드적으로 해결하거나 배열을 한번 더 붙이는 방식을 사용할 수 있다!
for문 대신 리스트 슬라이스를 사용하면 시간을 단축 시킬 수 있다.
defaultdict
윈도우 슬라이딩 기법

🍤 코드

n,d,k,c = map(int, input().split())
plate = []
for i in range(n):
    plate.append(int(input()))

max_sushi = 0

#방법1 (시간초과 실패)
for i in range(n):
    tmp = set()
    tmp.add(c)
    for j in range(k):
        tmp.add(plate[i-n+j])
    #print(tmp , end=' ')
    max_sushi = max(max_sushi, len(tmp))

#방법2
""" for i in range(n):
    if i <= n-k:
        tmp = set(plate[i:i+k])
    else:
        tmp = set(plate[i:])
        tmp.update(plate[:(i+k)%n])  # %나머지 기호를 잘 사용하자!
    #print(tmp, end=' ')
    tmp.add(c)
    #print(tmp)
    max_sushi = max(max_sushi, len(tmp)) """

print(max_sushi)

방법1로 했을 때는 시간초과로 실패가 되는데 for문 대신 슬라이스를 사용하였더니 정답이 됐다..!
아무래도 N의 최대가 30,000, k의 최대 3000이라서 시간초과가 되는 것 같다..

백준 15961번

같은 회전초밥 문제지만 접시의 갯수 범위가 확 커졌다.
따라서 슬라이딩 윈도우 방식으로 코드를 변경하였다.

Ref. 슬라이딩 윈도우란? https://learning-e.tistory.com/36
defaultdict란? https://docs.python.org/3/library/collections.html#collections.defaultdict

#방법3. 백준 15961번 슬라이딩 윈도우 기법
from collections import defaultdict
n,d,k,c = map(int, input().split())
arr = [ int(input()) for _ in range(n)]
arr = arr + arr[:k-1] 
max_sushi = 0
left , right = 0, 0
window = defaultdict()
window[c] +=1

while right < k:  #처음 k개로 초기값 만들기 
    window[arr[right]] +=1
    right+=1

for _ in range(n-1):
    max_sushi = max(max_sushi, len(window))    
    window[arr[right]] +=1
    window[arr[left]] -=1
    if window[arr[left]==0]: window.pop(arr[left])
    right+=1
    left+=1
print(max_sushi)