귀여운 라이언

문제분석

간단한 Two Pointer 문제이다.

9 3
1 2 2 1 2 1 2 1 1

위의 예시에 대해 아래의 그림을 보며 이해해보자.

빨간색 화살표는 Left Pointer, 파란색 화살표는 Right Pointer이다. 말 그대로 두개의 포인터를 사용해 탐색하는 것이다.

• 먼저 k개의 1을 포함하는 집합을 찾는다. 왼쪽부터 탐색해 나가면서, 제일 처음 등장하는 1의 위치에 빨간색 포인터를 위치시키고, k번째 나오는 1의 위치에 파란색 포인터를 위치시킨다. 이때 빨간색 포인터는 0, 파란색 포인터는 5에 위치함으로, 집합의 크기는 5-0+1=6이다.

• 두 포인터 사이에 위치하는 집합은 1가 k개 있다는 조건은 만족시키지만, 가장 짧은 집합인지는 아직 확실하지 않다. 따라서 포인터들을 옮기며 탐색해나간다.

• 빨간색 포인터를 다음으로 등장하는 1에 위치시키고, 파란색 포인터도 동일하게 다음에 등장하는 1의 위치에 위치시킨다. 이때, 포인터 좌표를 이용해 집합의 크기를 구하고, 최소 길이의 집합을 탐색해 나간다. 현재 빨간색 포인터는 3, 파란색 포인터는 7에 위치함으로, 집합의 크기는 7-3+1=5이다. 집합의 최소길이는 min(5,6)=5이다.

• 이 과정을 파란색 포인터(오른쪽 포인터)가 인형의 종류가 주어진 리스트의 크기를 벗어날 때 까지 반복해준다.

위와 같은 생각은 금방 할 수 있었는데, Two Pointer 문제가 처음이라서 그런지 코드로 작성하는데 굉장히 애를 먹었다. 일주일 후에 다시 풀며 최적화시켜 봐야겠다.

CODE

import sys
read=sys.stdin.readline

n,k=map(int,read().split())
if k ==0:
    print(0)
    sys.exit()
num=list(map(int,read().split()))

l,r,cnt=0,0,0

for i in range(n):
    if num[i]==1:
        l=i
        break
tmp=0
for i in range(i,n+1):
    if i == n:
        print(-1)
        sys.exit()
    if num[i]==1: tmp+=1
    if tmp==k:
        r=i
        break

answer=r-l+1
flag=1
while flag==1:
    for i in range(l+1,n):
        if num[i]==1:
            l=i
            break
    for i in range(r+1,n+1):
        if i == n:
            flag=2
            break
        if num[i]==1:
            r=i
            break
    if flag==1: answer=min(answer,r-l+1)

if answer < 2147000000:
    print(answer)
else: print(-1)

틀린 부분이 있을 수 있습니다. 피드백 주시면 고치도록 하겠습니다! 감사합니다.👍

[꼭 다시 풀어보기]