[BOJ][C++] 백준 15565번: 귀여운 라이언

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

 

문제

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

입력

첫 줄에 N과 K가 주어진다. (1 ≤ K ≤ N ≤ 106)

둘째 줄에 N개의 인형의 정보가 주어진다. (1 또는 2)

출력

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

 

풀이

프로그래머스 아닌 백준에 라이언 나와도 되는거임?

전형적인 투포인터 문제

단 포인터를 움직이면서 연산할 때 더하기와 빼기를 조건에 맞게 잘 해야하니 주의하자

// 풀이 : https://whkakrkr.tistory.com

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int>v(n);
    for(int i=0; i<n; i++) {
        cin >> v[i];
    }
    
    int left=0, right=0;
    int cnt = v[left]==1 ? 1 : 0;
    int ans = n+1;
    while(left<=right && right<n) {
        if(cnt>=k) {
            ans = min(ans, right-left+1);
            cnt -= v[left]==1 ? 1 : 0;
            left++;
        } else {
            right++;
            cnt += v[right]==1 ? 1 : 0;
        }
    }
    
    if(ans==n+1) {
        ans = -1;
    }
    cout << ans;
    
    return 0;
}