2 2 1 2 1 2 2 1 2 2 1 (크기 : 11)
k=3인 경우 라이언 인형이 3개 이상 존재하는 '가장 작은' 연속된 집합의 크기를 구하라는 문제다.
여기서 키 포인트는 '가장 작은'이 된다.
위 배열의 경우 만약 '가장 큰' 연속된 집합의 크기를 구하는 문제였다면 배열 전체가 답이 된다. 하지만 가장 작은 집합의 크기를 구하라고 했기 때문에 범위가 1 2 1 2 2 1로 좁혀진다.
결국 처음 등장하는 1부터 마지막 k번째로 등장하는 1의 위치를 구해서 범위를 구하면 그것이 답이 되는 문제이다.
입력 배열을 담을 v와 1의 위치 인덱스를 담을 ones를 선언한다.
입력 받을 때마다 1이라면 그 위치를 push해준다.
만약 k보다 1의 개수가 작으면 답을 구할 수 없기 때문에 바로 리턴을 때려준다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
ios::sync_with_stdio(0);
cout.tie(0);
cin.tie(0);
int n, k;
cin >> n >> k;
vector<int> v(n);
vector<int> ones;
for (int i = 0; i < n; i++)
{
cin >> v[i];
if (v[i] == 1)
ones.push_back(i);
}
int ans = 1000001;
if (ones.size() < k)
{
cout << -1;
return 0;
}
for (int i = 0; i <= ones.size() - k; i++)
ans = min(ans, ones[i + k - 1] - ones[i] + 1);
cout << ans;
return 0;
}