[백준2531/실1] 회전초밥 - Python

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

 

 

 

처음엔 그냥 비교할 대상을 덱에 넣고 뺴면서 검사만 해주면 된다고 생각했는데 시간이 너무 오래걸렸다.

 

 

첫번째 코드 (python 35316KB, 3496ms | pypy 178300KB, 2200ms)

1. deque에 k개의 초밥 올리기

2. 최댓값인지 비교

3. deque에 popleft 후 append 하면서 다음 비교 준비

# python 35316KB, 3496ms
# pypy 178300KB, 2200ms

from collections import deque

# 연속해서 초밥 k개 먹으면 쿠폰번호 초밥 하나 공짜
# result = 초밥 가짓수의 최댓값

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

arr = deque(sushi[:k])
max_num = 0


for i in range(N):

    cur_arr = set(arr) # 현재 연속한 초밥
    num = len(cur_arr) # 초밥 수

    if c in cur_arr:
        max_num = max(max_num, num)
    else:
        max_num = max(max_num, num + 1)

    # 다음 초밥 비교 준비
    arr.popleft()
    arr.append(sushi[(i+k) % N])

print(max_num)

 

 

 

그래서 어쩌지~~~~ 하다가 딕셔너리로 변경했다

 

두번째 코드 (python 34924KB, 836ms)

1. defaultdict에 k개의 초밥 접시 카운트

2. 최댓값인지 비교

3. defaultdict에 왼쪽 초밥 뺴고, 오른쪽 초밥 올리기

from collections import defaultdict

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

# 초기 deque에서 dict로 변경
sushi_count = defaultdict(int)

for i in range(k):
    sushi_count[sushi[i]] += 1
sushi_count[c] += 1  # 쿠폰 초밥 포함


max_num = len(sushi_count)


for i in range(N):
    
    # 맨 앞 초밥 제거
    left = sushi[i]
    sushi_count[left] -= 1
    if sushi_count[left] == 0:
        del sushi_count[left]

    # 맨 뒤 초밥 추가
    right = sushi[(i + k) % N]
    sushi_count[right] += 1

    max_num = max(max_num, len(sushi_count))

print(max_num)

 

 

 

초기에 deque으로 설정하고 풀었을 때는 시간복잡도가

O(k * N) : set으로 변경 작업 O(k)를 N번 반복

이었는데 dict로 바꾸고 나니

O(k)로 훨씬 단축됐다.

k가 3000이라 딕셔너리로 푸는게 훨씬 짧았다