회전 초밥 (실버 1)

from sys import stdin

N, d, k, c = map(int, stdin.readline().split())

sushi = [int(stdin.readline()) for _ in range(N)]

def two_slide(front, k, N):
    first_start = front
    first_end = N - 1

    second_start = 0
    second_end = k - ((N - 1) - front) - 2

    return first_start, first_end, second_start, second_end

def analysis(sushi_lst, c):
    unique = len(list(set(sushi_lst)))
    if c not in sushi_lst:
        unique += 1
    return unique
    
max_sushi = 0
for i in range(N):
    front = i
    end = i + k - 1
    if end >= N:
        fs, fe, ss, se = two_slide(front, k, N)
        f_sushi = sushi[fs:fe+1]
        s_sushi = sushi[ss:se+1]
        f_sushi.extend(s_sushi)
        sushi_tmp = f_sushi
    
    else:
        sushi_tmp = sushi[front:end+1]

    how_many_sushi = analysis(sushi_tmp, c)
    max_sushi = max(max_sushi, how_many_sushi)

print(max_sushi)

원형구조이다. 문제의 취지는 index가 제한길이를 초과할 때 어떻게 처리하느냐에 대한 것이다. 경우를 두 가지로 나눈다.
1. 슬라이드의 마지막 인덱스가 리스트의 마지막 인덱스를 초과하지 않는 경우
2. 슬라이드의 마지막 인덱스가 리스트의 마지막 인덱스를 초과하는 경우

2번에 대한 구현이 중요하다. 2번에 해당할 경우 two_slide 함수를 호출해서 두개의 start, end 인덱스를 받아온다. 이 4개의 인덱스를 통해 두개의 리스트로 나누고, 2개의 리스트를 합쳐서 구현한다.

연속된 스시리스트가 구성되면 이것을 분석기능에 해당하는 analysis함수에 넣고 unique값을 리턴받는다. 슬라이드를 for문으로 움직이면서 받은 unique값의 max값을 갱신하며 max값을 확정해서 끝낸다.

#방법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)) 

나머지 기호를 사용한 간단한 풀이도 존재한다.

슬라이딩 윈도우 속도 업

위의 나의 코드는 속도가 4436ms로 느린 편이다. 사람들의 파이썬 풀이의 대부분이 4자리수 이상의 속도를 보이고 있었다. 슬라이딩 윈도우를 만들때의 방식을 다르게 적용하면 속도를 단축할 수 있다.

from sys import stdin
from collections import defaultdict
N, d, k, c = map(int, stdin.readline().split())

sushi = [int(stdin.readline()) for _ in range(N)]

window = [sushi[x] for x in range(k)]
sushi_dict = defaultdict(int)
sushi_dict[c] = 1

def counting(sushi_dict):
    count = len(sushi_dict)
    return count

for i in window:
    sushi_dict[i] += 1
    

max_sushi = counting(sushi_dict)

for i in range(k,N+k-1):
    end = i

    if end > N-1:
        end = (end % N)
    
    out_ = sushi[end-k]
    in_ = sushi[end]
    
    sushi_dict[out_] -= 1
    if sushi_dict[out_] == 0:
        sushi_dict.pop(out_)
    sushi_dict[in_] += 1
    max_sushi = max(max_sushi, counting(sushi_dict))

print(max_sushi)

위의 방식과 다른 점은 위의 코드의 경우 window를 만들 때 기존 전체 회전초밥에 대해서 window범위에 해당하는 부분집합에 해당하는 window를 계속 찍어내고 있다. 즉 O(N^2)의 시간복잡도를 가진다. 하지만 아래의 경우는 중복되는 계산을 피하기 위해 기존의 window를 유지한 채 가장 왼쪽의 요소를 버리고 오른쪽에 새로운 요소를 추가한다. 만약 window의 길이가 3000이라면 3000씩 계속 새로 계산하는 것이 아니라 3000길이의 배열의 양끝의 수만 바꾸어서 진행하는 것이다.

사실 이것으로 N이 매우 늘어난, 다른 것은 같은 조건의 골드4문제를 풀려고 했는데 파이썬으로는 불가능할 듯 하다..