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

www.acmicpc.net/problem/14465

14465번: 소가 길을 건너간 이유 5

 

import sys
input = sys.stdin.readline

N,K,B = map(int,input().split())

arr = [0]*(N+1)

for i in range(B):
    arr[int(input())] = 1

s=[]
cnt = 0
for i in range(N+1):
    cnt+=arr[i]
    s.append(cnt)

answer = B
for i in range(N+1-K):
    answer = min(answer,s[i+K] - s[i])

print(answer)

풀이1 (누적합)

연속하는 K 개의 신호등을 만들 수 있는 신호등의 수

 

arr[n] = 0~n까지 신호등 수를 기록하는 부분합 배열을 만든다.

 

k ~ n 까지 진행하면서 arr[n] - arr[n-k] 가 최소인 값을 찾는다.

 

시간 복잡도

누적합으로 구하지 않고 각 영역(1~6,2~7...)을 sum(1:6) 같은 코드를 사용해서 구현했다면

연속되는 범위가 k라고 할때 합을 구할 때 O(k)가 발생한다.

합을 구하는 연산이 O(N)번 일어나서 O(kN) 이 될 것이다.

 

부분합 이용해 합을 구하는 과정을 O(1)로 줄일 수 있고 그것을 N번 수행하니

시간복잡도는 O(N)이다.

 

import sys
input = sys.stdin.readline

N,K,B = map(int,input().split())

arr = [0]*(N+1)

for i in range(B):
    arr[int(input())] = 1

s,e = 1,K
total = sum(arr[s:e+1])

answer = B
while True:
    if arr[s] == 1:
        total-=1
    e+=1
    s+=1

    if e == N+1:
        break

    total += arr[e]

    answer = min(total,answer)

print(answer)

풀이2 (슬라이딩 윈도우)

k의 크기를 가진 슬라이드를 만든다.

 

나는 s,e를 지정해 슬라이드 시작지점과 끝지점의 인덱스를 구해주었다.

 

먼저 시작지점의 고장난 신호등의 수(total)를 구한다.

 

시작지점(s)과 끝지점(e)을 구간의 끝까지 1씩 더하며 최솟값을 찾는다.

 

시작지점이 고장난 신호등 이었다면 1을 빼주고 추가되는 인덱스가 고장난 신호등이라면 1을 더해주면 된다.

 

시간복잡도

0~N+1 구간을 슬라이딩 윈도우로 한번 진행하면 답을 구할 수 있다.

즉 O(N) 이다.