[Python][백준] 15961번 회전 초밥

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

공부 날짜 : 2023.02.14
정답 참조 여부 : X

회전 초밥에서 연속된 접시 k개를 먹고 별도로 쿠폰 c번 스시를 먹을 때 가장 다양하게 먹을 수 있는 스시의 종류를 출력하는 문제이다.

---

이런 형태의 문제를 많이 풀어봤는데 이게 슬라이딩 윈도우라는 개념인줄 몰랐다.

특정 구간을 연속해서 탐색할 때 중복되는 구간은 유지하고, 다음 구간에 추가되는 요소를 더하고, 기존구간에서 중복되지 않는 요소는 빼는 방식으로 연산량을 줄이는 알고리즘이다.

이러한 방식을 많이 사용해 왔던터라 어렵지 않았다. 연속된 접시를 가지고 그때 접시의 종류를 체크하며, 최대값을 탐색했다.

종류를 세야하기 때문에 dict로 할까 생각 했었는데, key를 삭제하는 방법이 떠오르지 않아 리스트로 사용했다.

초밥의 종류가 d로 나오기 때문에 d+1의 크기인 리스트를 선언하고 구간에 포함되는 스시의 개수를 추가 해 줬다.

이때 그 스시의 개수가 원래 0이었으면 종류가 +1 되고, 스시를 뺄 때 원래 1이었으면 종류를 -1 해줬다.

마지막으로 해당 조합에서 쿠폰스시가 포함이 되어있는지 여부에 따라서 최대값을 갱신시켜 주었다.

소스코드

import sys
input = sys.stdin.readline
##############################################
n, d, k, c = map(int, input().split())

# 레일 위의 스시를 나타내는 리스트
sushi = []
for _ in range(n):
    sushi.append(int(input()))

# d종류의 스시에 대해서 선택한 연속된 k에 포함된 개수
check_dish = [0 for _ in range(d+1)]


# 처음부터 k개의 접시를 고른 경우
count = 0
for i in range(k):
    # 만약 이번에 추가된 접시가 이전에 고른 스시가 아닌경우 개수 추가
    if check_dish[sushi[i]] == 0:
        count += 1
    check_dish[sushi[i]] += 1

    # count의 최대값이 저장될 변수
    # 쿠폰 스시 포함 여부에 따라 개수를 추가하여 초기화
    if check_dish[c] == 0:
        answer = count + 1

    else:
        answer = count


# 초기 상태에서 다음 접시를 추가하고 첫 접시를 제거
# 0~k-1번까지 k개 고른뒤 k번째 접시를 넣고, 0번째 접시를 제거
for i in range(k, n + k - 1):
    # 만약 이번에 추가된 접시가 이전에 고른 스시가 아닌경우 개수 추가
    if check_dish[sushi[i % n]] == 0:
        count += 1
    check_dish[sushi[i % n]] += 1

    # 이번에 빠진 스시가 1개만 있었으면 개수 빼기
    if check_dish[sushi[i - k]] == 1:
        count -= 1

    check_dish[sushi[i - k]] -= 1

    # 쿠폰으로 받는 스시가 지금 고른 접시중에 포함 안되어 있으면
    # count +1개와 answer를 비교해서 갱신
    if check_dish[c] == 0:
        answer = max(answer, count + 1)

    # 아니면 그냥 갱신
    else:
        answer = max(answer, count)

# count 최댓값 출력
print(answer)