[BOJ] 15565번_귀여운 라이언_두 포인터 (C++)

[문제]

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

일렬로 라이언 인형과 어피치 인형이 놓여 있을 때 라이언 인형이 K개 이상 있는 가장 작은 연속된 집합의 크기를 구하는 문제이다.

[사용 알고리즘]

두 포인터

[풀이 핵심]

• 두포인터를 이용해서 배열을 탐색하는 방법을 사용하면 된다.

  1. start와 end라는 2개의 포인터를 0을 가르키도록 초기화해준다.
  2. start와 end 사이의 라이언 개수가 K개가 될 때까지 end를 늘려주고, 라이언이 K개가 됐을 때 집합의 크기을 저장해준다.
  3. 배열의 끝(총 인형의 개수)까지 계속해서 start를 늘려서 집합의 크기를 줄이고, end를 늘려 라이언 인형 개수를 K개로 맞추면서 계속해서 가장 작은 집합의 크기를 갱신해주면 답을 구할 수 있다.

[코드]

//boj15565번_귀여운 라이언_두 포인터

#include<iostream>

using namespace std;

int arr[1000001];

int main() {
	int N, K;
	cin >> N >> K;

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

	int start = 0;
	int end = 0;
	int lion = 0;
	int result = 9999999;

	while (end <= N + 1) {
		if (lion < K) {
			if (arr[end] == 1) {
				lion++;
			}
			end++;
		}
		else if (lion == K) {
			result = min(result, end - start);

			if (arr[start] == 1) {
				lion--;
			}
			start++;
		}
		else {
			if (arr[start] == 1) {
				lion--;
			}
			start;
		}
	}
	if (result == 9999999) {
		cout << -1;
	}
	else {
		cout << result;
	}

	return 0;
}