[BOJ 20922] 겹치는 건 싫어 C++/Kotlin

 

20922번: 겹치는 건 싫어

 

문제풀이

 

같은 원소가 K개 이하로 들어 있는 최장 연속 부분 수열의 길이를 구하는 문제다.

 

이중 for문으로도 해결할 수도 있지만 시간복잡도가 O(n^2)이기 때문에 시간초과가 발생할 가능성이 크다.

이럴 때는 투 포인터를 이용하면 시간복잡도를 O(N)으로 단축시킬 수 있다.

 

 

먼저 과정을 정리해보자면, 다음과 같다.

 

1. left, right 모두 0에서 시작한다.
2. cnt[arr[right]]이 K 미만이면 cnt 증가시키고 수열 길이를 갱신한 다음 right++
   K 이상일 경우 cnt 감소시키고 left++
3. right < n일 때까지 2번 과정을 반복

 

예시로 길이가 9인 수열 a = { 3, 2, 5, 5, 6, 4, 4, 5, 7 }에서 같은 원소가 2개 이하로 들어 있는 최장 연속 부분 수열의 길이를 구하는 과정을 살펴보자. (N = 9, K = 2)

 

 

이 문제의 경우 포인터 2개가 같은 방향으로 진행해나간다.

따라서 시작지점과 끝지점을 가리키는 포인터 left, right는 모두 0이다.

cnt 배열에는 각 원소값을 인덱스로 해당 부분 수열에 포함되어 있는 해당 원소의 개수를 저장한다.

처음 상태는 아래 그림과 같다.

 

 

 

현재 부분 수열은 빈 상태이므로 a[right]인 3의 개수는 0이다.

3을 추가하더라도 K개 이하이므로 부분 수열에 추가하고 cnr[3]과 right는 증가시킨다.

현재 최장 연속 부분 수열의 길이는 1이다.

 

2, 5도 마찬가지로 진행한다.

a[2]까지 진행하면 최장 연속 부분 수열의 길이는 3이 된다.

 

 

이제 a[3]을 추가하려 하는데 cnt[5]가 1이므로 하나 더 추가할 수 있다.

그리고 현재 최장 연속 부분 수열의 길이는 4가 된다.

a[6]까지 진행하면 아래 그림과 같다.

이때까지의 최장 연속 부분 수열의 길이는 7이다.

 

 

이제 5를 추가하려 하는데 이미 부분 수열에 5가 2개 들어있다.

따라서 5를 추가하지 않고 cnt[5]가 K 미만이 될 때까지 a[left]를 제거한다.

 

5의 개수가 1이 되었으므로 추가할 수 있게 되었다.

최장 부분 수열의 길이가 이전보다 더 길면 갱신시켜주고 cnt[5]와 right를 증가시킨다.

 

마지막 원소인 7까지 부분 수열에 추가하면 반복문을 종료한다.

 

최종적으로 최장 연속 부분 수열의 길이는 7이 된다.

 

 

코드

 

C++ 코드

 

	#include <iostream>
	#include <algorithm>
	#define AMAX 200001
	#define DMAX 100001
	using namespace std;
	int arr[AMAX];
	int dup[DMAX];
	int main()
	{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, k;
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
	cin >> arr[i];
	}
	int answer = 0;
	int left = 1;
	int right = 1;
	while (left <= right && right <= n) {
	if (dup[arr[right]] < k) {
	dup[arr[right++]]++;
	answer = max(answer, right - left);
	}
	else if (dup[arr[right]] == k) {
	dup[arr[left++]]--;
	}
	}
	cout << answer;
	return 0;
	}

view raw [BOJ 20922] 겹치는 건 싫어.cpp hosted with ❤ by GitHub

 

Kotlin 코드

 

	fun main() = with(System.`in`.bufferedReader()) {
	val (n, k) = readLine().split(" ").map { it.toInt() }
	val arr = readLine().split(" ").map { it.toInt() }
	val cnt = IntArray(100001) // 수열에 속한 각 원소의 개수
	var (left, right) = arrayOf(0, 0)
	var answer = 0
	while (right < n) {
	if (cnt[arr[right]] < k) { // k 미만일 때만 추가 가능
	cnt[arr[right]]++
	answer = maxOf(answer, right - left + 1)
	right++
	} else { // 같은 원소가 k 이상 들어있으면 하나씩 제거
	cnt[arr[left]]--
	left++
	}
	}
	println(answer)
	}

view raw [BOJ 20922] 겹치는 건 싫어.kt hosted with ❤ by GitHub