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

문제

15565번: 귀여운 라이언

풀이

두 포인터, 슬라이딩 윈도우 문제이다. 

 

• 라이언의 인덱스를 따로 벡터에 저장한다. 
• 벡터의 길이가 K보다 작은 경우 집합을 만들 수 없다. 
• 크기가 K로 고정된 슬라이딩 윈도우 방식으로 벡터를 순회하면서 집합의 최소 크기를 탐색한다. 
• i에서 부터 i + K - 1까지의 원소의 수는 K개이다. 
• lion[i + K - 1] - lion[i] + 1이 lion[i]를 첫 요소로하며 크기가 K인 집합의 크기이다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

int nums[1000001];
vector<int> lion;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, K;
    cin >> N >> K;

    for (int i = 0; i < N; ++i)
    {
        cin >> nums[i];

        // 라이언의 인덱스를 따로 저장한다.
        if (nums[i] == 1)
        {
            lion.push_back(i);
        }
    }

    // 라이언의 수가 K보다 작은 경우 집합을 만들 수 없다.
    if (lion.size() < K)
    {
        cout << "-1";
        return 0;
    }
    
    // 크기가 K로 고정된 슬라이딩 윈도우 방식
    // i에서 부터 i + K - 1까지의 원소의 수는 K개이다.
    // lion[i + K - 1] - lion[i] + 1이 lion[i]가 첫 요소이고 lion[i + K - 1]이 마지막 요소인 집합의 길이이다.
    int answer = INT_MAX;
    for (int start = 0; start < lion.size() - K + 1; ++start)
    {
        int end = start + K - 1;   
        
        answer = min(answer, lion[end] - lion[start] + 1);
    }

    cout << answer;

    return 0;
}