[백준] 2531 회전 초밥(파이썬/python)

🎈문제

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

 

🎁알고리즘 및 접근

브루트포스

1. 모든 경우의 수를 다 탐색해 보아야한다.

2. 이때, 2중 for문과 set을 활용해서 탐색했으나 시간초과가 났다.

3. defaultdict를 사용해서 시간이 오래 걸리는 set을 사용하지 않고, for문 하나로 탐색 가능했다.

 

💻정답 코드

# 2531 회전 초밥

from collections import defaultdict
# import sys
# input = sys.stdin.readline()

n,d,k,c = map(int,input().split())
sushi = [int(input()) for _ in range(n)]
eat = defaultdict(int)
eat[c] += 1 # 쿠폰으로 받은 초밥은 먹은 것으로 초기화

# 초기 k개의 초밥 먹은 것으로 설정 후 시작
for i in range(k):
    eat[sushi[i]] += 1
answer = len(eat)   # 초밥 최소 개수 초기화

for i in range(n):
    # 위에서 0~k번을 골랐다면 1~(k+1)번을 고르기 위해 0번 초밥을 빼줌
    eat[sushi[i]] -= 1
    # 해당 초밥이 0값이 되면 안먹은 것이 되므로 dictionary에서 빼줌
    if eat[sushi[i]] == 0: 
        del eat[sushi[i]]   # dictionary의 길이로 초밥 종류 개수를 세므로 제거

    eat[sushi[(i+k)%n]] += 1    # (k+1)번 초밥 추가

    answer = max(answer,len(eat))   # 최대 초밥 개수 갱신

print(answer)

🎄코드 설명

주석으로 설명은 대체한다.

 

 

❗ 시간 초과 코드

# 2531 회전 초밥 -> 시간 초과

# import sys

# input = sys.stdin.readline()

n,d,k,c = map(int,input().split())
sushi = [int(input()) for _ in range(n)]
cnt = 0

for i in range(n):
    combi = set()

    for j in range(i,i+k):
        combi.add(sushi[j%n])

    len_combi = len(combi)

    if c in combi:
        cnt = max(cnt,len_combi)
        continue
    cnt = max(cnt,len_combi+1)

print(cnt)