15565

날짜 : 2023. 01. 30

사용 언어 : python

 

문제

 

 

코드

import sys

n, k = map(int, sys.stdin.readline().split())  # 인형의 개수, 라이언 개수
doll = list(map(int, sys.stdin.readline().split()))

ryan = list()
for i in range(n):
    if doll[i] == 1: ryan.append(i)  # 라이언 위치 저장
#print(doll)
#print(ryan)

if len(ryan) < k: # 조건미달
    print(-1)
    exit()

res = int(1e9)
for i in range(len(ryan)-(k-1)):
    #print(ryan[i+(k-1)], ryan[i])
    res = min(res, ryan[i+(k-1)] - ryan[i] + 1)  # 거리 계산
print(res)

 

 

풀이

- 인형의 개수와 라이언의 개수를 입력받고 이후 각 인형의 배치를 입력받는다.

- 수열이 최소가 되는 경우는 라이언의 개수를 최소한으로 한 경우이기 때문에 라이언의 개수를 k만큼 늘렸을 때의 인덱스로 비교한다.

- 일반 for문을 통해 라이언의 위치를 구한 후 각 로케이션을 토대로 인덱스끼리 빼면서 비교하는 방식으로 최솟값을 갱신해 나간다. (그리디를 활용해서 풀이)

 

알게된 점

- 알고리즘 오카방에 올라온 문제기도 하고 티어가 실버라서 건드려봤는데 되려 풀이가 쉽게 풀려서 조금 의아했던 문제였다.

- 슬라이딩 윈도우를 활용한 문제였는데 단순 그리디로 풀려서 근무시간에 조금 뭐지? 했던거같다.

- 아아 아닌거같다. 아마 은연중에 슬라이딩 윈도우를 사용한듯....

 

 

참고 사이트

-