BOJ 15565 귀여운 라이언

5832 단어 2021.03.192021.03.19

https://www.acmicpc.net/problem/15565
시간 1초, 메모리 256MB
input :

  • N, K (1 ≤ K ≤ N ≤ 10^6)
  • N개 인형의 정보(1 또는 2)

output :

  • K개 이상의 라이언 인형을 포함하는 가장 작은 연속된 인형들의 집합의 크기를 출력한다. 그런 집합이 없다면 -1을 출력

투 포인터를 이용해서 cnt 변수로 라이언 인형의 개수를 기록하고 cnt == k 일 때 ans 를 length 와 비교하며 업데이트 해주자.

그리고 예외적으로 end 포인터가 n 이 되었을 떄, cnt < k 라면 어차피 조건을 성립할 수 없으 니까 break를 걸자.

import sys

n, k = map(int, sys.stdin.readline().split())
data = list(map(int, sys.stdin.readline().split()))

start, end, cnt, length = 0, 0, 0, 0
ans = float('inf')

while start <= end:
    if end == n:
        if cnt < k:
            break
        ans = min(ans, length)
        if data[start] == 1:
            cnt -= 1
        length -= 1
        start += 1
        continue

    if cnt < k:
        if data[end] == 1:
            cnt += 1
        length += 1
        end += 1
    else:
        ans = min(ans, length)
        if data[start] == 1:
            cnt -= 1
        length -= 1
        start += 1
        
print(-1 if ans == float('inf') else ans)

-1을 출력해 줘야 하는 것을 간과 하고 한 번 틀리고 2번째는 float('int')라고 쓰는 바람에 틀렸다.....

좋은 웹페이지 즐겨찾기