[Baekjoon 2531 / python / 실버1] 회전 초밥

문제

 

투 포인터 문제이다.

근데 해결방법 고민 하는데 시간복잡도도 그렇고 그냥 구현해도 될 거 같아서 해봤는데 풀려버렸다...

 

결론은 투 포인터 안 쓰고 그냥 구현으로 풀었다.

 

# 실버1 -> 투 포인터

"""

N : 회전 초밥 벨트에 놓인 접시의 수

D : 초밥의 가짓수(초밥 최대 번호)

K : 연속해서 먹어야 하는 접시의 수

C : 쿠폰으로 먹을 수 있는 초밥 번호

"""

import sys

input = sys.stdin.readline

N, D, K, C = map(int, input().split())

sushi = [int(input()) for _ in range(N)]

count = 0

for start in range(N):

   

    choice = [sushi[(start + i) % N] for i in range(K)]

    choice.append(C)

   

    unique_choice = set(choice)

    unique_choice_length = len(unique_choice)

    # 결과 갱신

    count = max(unique_choice_length, count)

print(count)

 

정말 문제에 나온 그대로 구현을 했다.

 

회전 초밥이기 때문에 처음과 끝이 연결되어 있어야 하므로, choice를 할당할 때 나머지 값을 이용했다.

또한 set으로 중복을 제거했는데, 제거하기 전에 항상 C(쿠폰)을 추가해 주었다. 쿠폰은 무조건 먹는거고, 이미 먹은거라고 해도 어차피 중복제거 하면 사라지니까.

 

마지막으로 중복제거 한 집합의 길이를 구하고, 결과값을 max 함수로 비교해 매번 갱신해 주면 된다.

 

 

참고로 Python3으로 제출하면 시간 초과다 PyPy3 으로 제출해야 겨우 턱걸이 통과한다.

 

결과