[알고리즘 문제 풀이][슬라이딩 윈도우] 백준 15961번

[알고리즘 문제 풀이][슬라이딩 윈도우] 백준 15961번 - 회전 초밥

초코쨔응 2022. 1. 5. 00:02

백준 15961번 회전 초밥 문제입니다.

(투 포인터 & 슬라이딩 윈도우)

- 문제 설명: https://www.acmicpc.net/problem/15961

- 문제 풀이:

회전 초밥 접시들을 연속해서 k 개씩 먹고, c 라는 초밥을 하나 먹을 수 있는 쿠폰이 있을 때, 최대의 가짓수를 찾아야합니다. 최대의 가짓수를 위해서는 일반적으로 k 개 먹은 초밥 중에 같은 번호의 초밥이 하나도 없어야합니다. 또한 c 쿠폰을 사용할 수 있도록 c 라는 번호의 초밥도 없어야합니다.

sliding window 라는 방법으로, k 개 범위를 한칸씩 이동하면서 해당 범위 안에 초밥 가짓수가 줄어들었는지, 증가했는지를 체크합니다.

- 코드:

N, d, k, c = map(int, input().split())
dish = []
eat = [0]*(d+1)
for _ in range(N):
    dish.append(int(input()))

# 초기 k 접시 & c 쿠폰 사용
ans = 0
cur = 1
eat[c] += 1
for i in range(k):
    eat[dish[i]] += 1
    if eat[dish[i]] == 1:
        cur += 1
ans = cur

for i in range(1, N):
    _prev = (i-1) % N
    _next = (i-1+k) % N
    
    # sliding window 벗어난 범위 -1
    eat[dish[_prev]] -= 1
    if eat[dish[_prev]] < 1:
        cur -= 1

    # sliding window 들어오는 범위 +1
    eat[dish[_next]] += 1
    if eat[dish[_next]] == 1:
        cur += 1

    if ans < cur:
        ans = cur
    
print(ans)

- 실수 포인트 & 반례:

1. 회전 초밥인데, 회전을 고려하지 않는 경우

인덱스에서 % n 을 해서 한바퀴를 도는 경우를 고려해야합니다. n-1 인덱스를 시작점으로 k 개 범위가 잡힌 경우도 고려해야합니다.

2. 최대 가짓수 체크를 잘못하는 경우, 가짓수가 계속 감소하거나 증가할 수 있습니다

(아래는 4개 구간마다 계속 9 가 나오도록 만든 반례입니다, 제 틀린 코드에서는 계속 증가하다가 7이 출력되었습니다)