[백준 15565] 귀여운 라이언 (Python)

www.acmicpc.net/problem/15565

15565번: 귀여운 라이언

 

문제풀이

N, K, arr : 입력값

left, right : 투 포인터

q : 집합을 담는 deque

cnt : 1의 개수

ans : 1이 K개 일때의 집합의 최소 길이

 

기초 투 포인터(Two-Pointer) 문제였다. 쉬운 문제였는데, 처음에 left, right 만으로 집합의 길이 계산하려다가 계속 에러나서 문제 푸는데 오래걸려서, 그냥 deque 사용해서 해결하였다. 이 정도의 문제는 정말 빠르게 해결할 필요가 있는데, 반성하게 되었다. ㅠㅠ 

또한 문제 조건에 불가능한 경우 -1 출력하라 했는데, 해당 예외 처리 하지 않아서 처음에 틀렸습니다 를 받았다. 문제 끝까지 제대로 읽어야한다... ㅠㅠ

 

1. 1의 개수(cnt)가 K 일때까지 right를 증가시키면서 q 에 arr[right]를 넣어준다.

 

2. cnt가 K일 경우 그때의 q의 길이와 ans를 비교하여 더 작은 값으로 ans를 변경한다.

- 이후 최소 길이를 찾기 위해 left를 증가하고 q의 가장 첫 원소를 뺼 것이다.

- arr[left]가 1일 경우 cnt를 1 감소한다.

- left를 1 증가하고 q에서 가장 앞에 있는 원소를 빼준다.

 

3. 결과를 출력한다.

 

코드

import sys
from collections import deque

if __name__ == '__main__':
    N, K = map(int, sys.stdin.readline().split())
    arr = list(map(int, sys.stdin.readline().split()))

    ans = sys.maxsize
    left, right = 0, 0
    cnt = 0
    q = deque()
    for start in range(N):
        while right < N and cnt < K:
            q.append(arr[right])
            if arr[right] == 1: cnt += 1
            right += 1
        if cnt == K:
            ans = min(len(q), ans)
            if arr[left] == 1: cnt -= 1
            left += 1
            q.popleft()
    print(ans if ans != sys.maxsize else -1)

 

결과

 

문제풀이나 코드에서 이상한 부분 지적은 언제나 환영합니다!