[Algorithm][BOJ 15565] (Python) 귀여운 라이언

링크

https://www.acmicpc.net/problem/15565

15565번: 귀여운 라이언

 

문제

꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자. 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 크기를 구하여라.

 

알고리즘

투 포인터

 

풀이 방법

입력받은 인형 리스트 안에서 라이언이 있는 인덱스만을 뽑은 후 슬라이딩 윈도우 이용

 

 

코드

import sys

input = sys.stdin.readline

[N, K] = list(map(int, input().split(' ')))
dollList = list(input().rstrip('\n').split(' '))

rionList = []

for idx, doll in enumerate(dollList) :
    if doll == '1' :
        rionList.append(idx)

if K > len(rionList) :
    print(-1)
else :
    lidx = 0
    ridx = K-1
    left = rionList[lidx]
    right = rionList[ridx]
    answer = right - left
    while True :
        lidx += 1
        ridx += 1
        if ridx == len(rionList) :
            break
        left = rionList[lidx]
        right = rionList[ridx]
        if right-left < answer :
            answer = right-left
    print(answer+1)

 

후기 및 보완할 점

코테 준비는 처음, 그래서 투 포인터랑 슬라이딩 윈도우 개념만 보고 구현했다.

그래서 코드가 조금 미흡한 점이 있다. 쓸데없이 뭔가 많이 쓴 느낌이랄까나

시간도 2시간 조금 안되게 걸린 것 같다.

투 포인터 위주로 한 문제 정도는 더 풀어봐야징.....