[BOJ] 2531번 회전 초밥 / 사용언어 : 파이썬(python)

※ 문제링크

2531번: 회전 초밥

※ 관련개념

슬라이딩 윈도우(Sliding Window)

해당 문제는 투 포인터에서 변형된 슬라이딩 윈도우 방식으로 해결할 수 있는 문제였다. 슬라이딩 윈도우를 간단하게 설명하면 포인터 2개를 통해 일정 구간의 범위를 유지한채로 탐색하는 방법이라고 이해하면 되겠다. 해당 개념에 대해 잘 설명해놓은 사이트가 있어서 링크를 걸어두었으니 좀 더 자세한 사항을 원하는 사람은 참고하면 좋을 것 같다. 해당문제를 풀기위해 생각해야할 부분은 원형연결리스트 형태의 자료구조를 어떻게 구현할 것인가였는데 이번에는 투 포인터의 한쪽끝이 리스트의 범위를 넘어가면 리스트의 크기만큼 빼고 탐색하는 방식으로 해결하였다. 자세한 풀이방법과 코드는 아래와 같다.

1. 입력받은 값을 각각의 변수에 저장하고, 회전초밥의 순서를 기록할 리스트를 작성한다.

2. 연속해서 먹을 수 있는 초밥의 가짓수 확인을 위해 2개의 포인터를 작성하고, set을 활용하여 초밥의 가짓수를 확인한다.

3. 1번 포인터가 N보다 크거나 같게되면 반복문을 종료하고, 2번 포인터가 N보다 크게되면 N을 빼준다.(원형연결리스트)

4. 반복문 종료 후 가장 큰 초밥의 가짓수를 출력해준다.(시간 및 메모리 단축을 위해 sys를 사용하였습니다.)

 

import sys
N, d, k, c = map(int, input().split()) # N: 접시의 수 / d: 초밥의 가짓수 / k: 연속해서 먹는 접시수 / c: 쿠폰 번호

# input = sys.stdin.readline
cp1, cp2 = 0, k-1
sushi = []
for _ in range(N):
    sushi.append(int(input()))
check = set()

while cp1 < N:
    if cp2 >= N:
        cp2 -= N
    if cp2 < cp1:
        plates = sushi[cp1:] + sushi[:cp2+1]
    else:
        plates = sushi[cp1:cp2+1]
    cases = set(plates)
    if c not in cases:
        cases.add(c)
    if len(check) < len(cases):
        check = cases
    cp1 += 1
    cp2 += 1
print(len(check))

 

P.S 더 나은 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.