[BOJ] 2531 - 회전 초밥 (🥈 실버 1티어, 슬라이딩 윈도우 알고리즘 🌟)

사용 언어: Python3, Java

문제

회전 초밥

풀이

나의 풀이

# 접시수, 초밥 가짓수, 연속해서 먹는 접시수, 쿠폰번호
N, d, k, c = map(int, input().split())
lst = [int(input()) for _ in range(N)]

sushi_kind_cnt = [] # 초밥 종류수
for i in range(N):
    lp = i
    rp = (lp + (k-1)) % N
    tmp = [] # 벨트의 임의의 한 위치부터 연속된 k개의 초밥
    for i in range(lp, rp + 1):
        tmp.append(lst[i])
    sushi_kind_cnt.append(len(set(tmp+[c])))

print(max(sushi_kind_cnt))

• 테스트 케이스: 성공
• 제출 결과: 시간초과

다른 풀이

참고

import sys
from collections import defaultdict
input = sys.stdin.readline

# N : 회전 초밥 벨트에 놓인 접시의 수
# d : 초밥의 가짓수
# k : 연속해서 먹는 접시의 수
# c : 쿠폰 번호
N, d, k, c = map(int, input().rstrip().split())
lst = list(int(input().rstrip()) for _ in range(N))

dic = defaultdict(int)
lp, rp = 0, k-1
for i in range(lp, rp+1):
    dic[lst[i]] += 1
dic[c] += 1 # 구간 내에 항상 쿠폰 번호 포함

mx = -1e9
while lp < N:
    mx = max(mx, len(dic))

    dic[lst[lp]] -= 1 # 왼쪽 접시 제거
    if dic[lst[lp]] == 0:
        del dic[lst[lp]]
    lp, rp = lp+1, rp+1
    dic[lst[rp % N]] += 1 # 오른쪽 접시 추가

print(mx)

• 테스트 케이스: 성공
• 제출 결과: 성공
• 슬라이딩 윈도우 알고리즘에 대해 궁금하다면 이 글을 참고하자!

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기