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

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

15565번: 귀여운 라이언

문제

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

 

---

 

라이언인형(=1)이 K개 이상인 연속의 그룹을 찾아야하는 문제이다.

완전탐색으로 해결할 경우 N의 제한이 10^6이기 때문에 시간초과가 발생하게 된다.

따라서 투 포인터로 조건에 해당하는 가장 작은 범위를 찾아가야 한다.

 

하나 실수했던 부분이 중복된 구간을 계속해서 추가하여 하나씩 출력해보면서 디버깅을 하였다.

중복된 구간의 인형은 세지 않도록 주의해야한다.

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <climits>
#include <set>
#include <map> 
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ll long long	
#define ull unsigned long long
#define INF 987654321
#define Mod 1000000009
#define endl '\n'
#define ENDL cout << endl

using namespace std;

int N, K;
vector<int> ps;
bool visited[1000000 + 1];
int parent[3];

void input() {
	cin >> N >> K;
	ps = vector<int>(N, 0);
	for (int i = 0; i < N; i++) {
		cin >> ps[i];
	}
}

int solution() {
	int answer = INF;
	if (N == 1) {
		return (K == 1 && ps[0] == 1) ? 1 : -1;
	}
	int pl = 0, pr = 1;
	visited[0] = visited[1] = true;
	parent[ps[pl]]++;
	parent[ps[pr]]++;

	while (pl < pr) {
		if (parent[1] >= K) {
			answer = min(answer, pr - pl + 1);
			parent[ps[pl]]--;
			pl++;
			if (!visited[pl]) {
				visited[pl] = true;
				parent[ps[pl]]++;
			}
		}
		else {
			pr++;
			if (pr == N) break;
			if (!visited[pr]) {
				visited[pr] = true;
				parent[ps[pr]]++;
			}
		}
	}

	return answer == INF ? -1 : answer;
}

int main() {
	fastio;
	input();
	cout << solution() << endl;

	return 0;
}