[백준/python] 2531 - 회전 초밥

첫번째 try

a = list(map(int, input().split()))
n = a[0]; d = a[1]; k = a[2]; c = a[3]
sushi = [
    input()
    for _ in range(n)
]
pointer = 0
case = []
for _ in range(n):
    if pointer + k <= n - 1:
        part = sushi[pointer:pointer + k]
        case.append(part)
        pointer += 1
    else:
        part = sushi[pointer:] + sushi[:pointer + k - n]
        case.append(part)
        pointer += 1
max = 0      
for set_case in case:
    set_case = set(set_case)
    leng = len(set_case)
    if str(c) not in set_case:
        leng += 1 
    if leng >= max:
        max = leng
print(max)

메모리 초과

 

두번째 try:

def leng(a, max):
    a = set(a)
    leng = len(a)
    if str(c) not in a:
        leng += 1 
    if leng >= max:
        max = leng   
    return max

a = list(map(int, input().split()))
n = a[0]; d = a[1]; k = a[2]; c = a[3]
sushi = [
    input()
    for _ in range(n)
]

pointer = 0
max = 0

for _ in range(n):
    if pointer + k <= n - 1:
        part = sushi[pointer:pointer + k]
    else:
        part = sushi[pointer:] + sushi[:pointer + k - n]
    max = leng(part, max)
    pointer += 1
print(max)

> 타임 아웃

세번재 try

from collections import deque
import itertools

def leng(a, max_a):
    a = set(a)
    a.add(str(c))
    leng = len(a)
    maxi = max(max_a, leng)
    return maxi

a = list(map(int, input().split()))
n = a[0]; d = a[1]; k = a[2]; c = a[3]
sushi = [
    input()
    for _ in range(n)
]
sushi_q = deque(sushi)

pointer = 0
max_sushi = 0

for _ in range(n):
    part = list(itertools.islice(sushi_q, 0, k))
    sushi_q.rotate(1)
    max_sushi = leng(part, max_sushi)
    pointer += 1
print(max_sushi)

네번째 try:

import sys
import itertools
from collections import deque
input = sys.stdin.readline


def leng(a, max_a):
    a = set(a)
    a.add(c)
    leng = len(a)
    maxi = max(max_a, leng)
    return maxi

n, d, k, c = map(int,input().split())

sushi = [
    int(input())
    for _ in range(n)
]
max_sushi = 0
sushi_q = deque(sushi)
sushi_q.extend(sushi)
pt = 0
for _ in range(n):
    part = list(itertools.islice(sushi_q, pt, pt + k))
    max_sushi = leng(part, max_sushi)
    pt += 1
print(max_sushi)

sys.stdin.readline와 deque를 써보았다. 그래도 타임아웃

sys.stdin.readline

https://velog.io/@yeseolee/Python-파이썬-입력-정리sys.stdin.readline

deque

https://goldory.tistory.com/62

https://wikidocs.net/104977

슬라이싱을 쓰면 안되나보다.

 

결국 참조

 

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

N, d, k, c = map(int,input().split()) # k = 연속해서 먹는 초밥 수, c = 쿠폰
sushi = [] 
for _ in range(N):
    sushi.append(int(input()))
sushi.extend(sushi) # 리스트를 두배로 만들어서 원형큐로 만듦

left = 0
right = 0
max_cnt = 0 # 최대 초밥 가지수
eat = defaultdict(int)

eat[c] += 1 # 미리 쿠폰을 하나 추가해둔다.

for right in range(len(sushi)):
    eat[sushi[right]] += 1 # eat 딕셔너리에 sushi[0~3], 즉 7, 9, 7, 30을 넣고 1을 추가
    if right >= k-1: # right 포인터가 3을 넘으면 최댓값 갱신
        max_cnt = max(max_cnt,len(eat))
        eat[sushi[left]] -= 1 # 다음 칸 넘어가기 위해서 sushi[0] 하나 줄이고
        if eat[sushi[left]] == 0: # 해당 초밥의 값이 0이면
            del eat[sushi[left]]
        left += 1 # left 한 칸 옆으로
print(max_cnt)

장고 공부하려고 딕셔너리 공부하고 있었는데 책에서 defaultdict에 대한 설명이 나와서 이해하지 못했던 혁신적인 코드를 이해함

defaultdict 은 딕셔너리에 존재하지 않는 키를 만들어주고 += 나 -= 연산을 통해서 값을 추가해주거나 뺀다. str도 가능

수행과정:

7/9/7/30

left -1 전 defaultdict(<class 'int'>, {30: 2, 7: 2, 9: 1}) left -1 후 defaultdict(<class 'int'>, {30: 2, 7: 1, 9: 1})

9/7/30/2 left -1 전 defaultdict(<class 'int'>, {30: 2, 7: 1, 9: 1, 2: 1}) left -1 후 defaultdict(<class 'int'>, {30: 2, 7: 1, 2: 1})

7/30/2/7 left -1 전 defaultdict(<class 'int'>, {30: 2, 7: 2, 2: 1}) left -1 후 defaultdict(<class 'int'>, {30: 2, 7: 1, 2: 1})

30/2/7/9 left -1 전 defaultdict(<class 'int'>, {30: 2, 7: 1, 2: 1, 9: 1}) left -1 후 defaultdict(<class 'int'>, {30: 1, 7: 1, 2: 1, 9: 1})

2/7/9/25 left -1 전 defaultdict(<class 'int'>, {30: 1, 7: 1, 2: 1, 9: 1, 25: 1}) left -1 후 defaultdict(<class 'int'>, {30: 1, 7: 1, 9: 1, 25: 1})

반복 left -1 전 defaultdict(<class 'int'>, {30: 1, 7: 2, 9: 1, 25: 1}) left -1 후 defaultdict(<class 'int'>, {30: 1, 7: 1, 9: 1, 25: 1})

left -1 전 defaultdict(<class 'int'>, {30: 1, 7: 1, 9: 2, 25: 1}) left -1 후 defaultdict(<class 'int'>, {30: 1, 7: 1, 9: 1, 25: 1})

left -1 전 defaultdict(<class 'int'>, {30: 1, 7: 2, 9: 1, 25: 1}) left -1 후 defaultdict(<class 'int'>, {30: 1, 7: 2, 9: 1})

left -1 전 defaultdict(<class 'int'>, {30: 2, 7: 2, 9: 1}) left -1 후 defaultdict(<class 'int'>, {30: 2, 7: 1, 9: 1})

left -1 전 defaultdict(<class 'int'>, {30: 2, 7: 1, 9: 1, 2: 1}) left -1 후 defaultdict(<class 'int'>, {30: 2, 7: 1, 2: 1})

left -1 전 defaultdict(<class 'int'>, {30: 2, 7: 2, 2: 1}) left -1 후 defaultdict(<class 'int'>, {30: 2, 7: 1, 2: 1})

left -1 전 defaultdict(<class 'int'>, {30: 2, 7: 1, 2: 1, 9: 1}) left -1 후 defaultdict(<class 'int'>, {30: 1, 7: 1, 2: 1, 9: 1})

left -1 전 defaultdict(<class 'int'>, {30: 1, 7: 1, 2: 1, 9: 1, 25: 1}) left -1 후 defaultdict(<class 'int'>, {30: 1, 7: 1, 9: 1, 25: 1})