[백준] 14465 소가 길을 건너간 이유

이 문제를 처음 접할 때 1. 그래프 이론 아니면 2. 합 연산 이라고 생각했는데 전혀 아니었다. 특이한 이론이니 기억해두도록 하자.

슬라이딩 윈도우

슬라이딩 윈도우는 이진탐색이나 투 포인터와 마찬가지로 left와 right변수를 이용해서 리스트를 탐색하는 기법이다.

그림과 같이 왼쪽 -> 오른쪽으로 탐색을 해도 되고, 그 반대로 해도 좋다. 암튼 이 문제는 이 기법을 사용해서 left와 right사이에 지정된 요소가 몇 개가 있는지 탐색하는 특이한 문제였다.

내가 푼 코드는 다음과 같다.

import sys

N, K, B = map(int, sys.stdin.readline().rstrip().split())
data = [1] * (N+1)

for i in range(B):
  data[int(sys.stdin.readline().rstrip())] = 0

broken = 0
min_value = K

for left in range(1, N+1):
  if left > (N - K + 1): # 데이터 검색 끝
    break
  else:
    right = left + K - 1 # right 값 갱신
    for item in data[left:right + 1]:
      if item == 0:
        broken += 1
      if broken >= min_value: # 최솟값보다 크게 나오면 바로 반복문 탈출 
        break
    min_value = min(min_value, broken)
    broken= 0 # 초기화시켜줌

print(min_value)