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

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

문제

---

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

 

입력

---

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

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

 

출력

---

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

 

문제 풀이

---

투포인터 슬라이딩 윈도우 문제.

처음 시작할 때 배열의 인덱스를 나타내는 start와 end를 각각 0으로 설정하고, start를 증가시키며 라이언 인형의 개수가 K가 될 때까지 end를 증가시킨다. 라이언 인형의 개수가 K가 되었다면 가장 작은 집합의 크기와 비교하여 더 작은 값을 저장한다. start를 증가시킬 때 현재 배열[start]가 라이언 인형인 1이라면 start를 증가시키고 난 후는 라이언 인형의 개수가 1 감소되어야 한다.

 

아래는 코드.

#include <iostream>
#include <algorithm>
#define MAX 987654321
using namespace std;

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N, K;
	cin >> N>>K;
	int* arr = new int[N];
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
	int start = 0;
	int end = 0;
	int lionCount = 0;
	int minLength = MAX;
	while (start < N)
	{
		while (end < N && lionCount !=K)
		{
			if (arr[end] == 1)
			{
				lionCount++;
			}
			end++;
		}
		if (lionCount == K)
		{
			minLength = min(minLength, end - start);
		}
		if (arr[start] == 1)
		{
			lionCount--;
		}
		start++;
	}
	if (minLength == MAX)
	{
		cout << -1 << "\n";
	}
	else
	{
		cout << minLength << "\n";
	}
	return 0;
}