백준 20922 겹치는 건 싫어 c++, Kotlin (투 포인터)

문제 출처 : https://www.acmicpc.net/problem/20922

20922번: 겹치는 건 싫어

문제

홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 K$K$개 이하로 들어 있는 최장 연속 부분 수열의 길이를 구하려고 한다.

 100000$100\,000$ 이하의 양의 정수로 이루어진 길이가 N$N$인 수열이 주어진다.  이 수열에서 같은 정수를 K$K$개 이하로 포함한 최장 연속 부분 수열의 길이를 구하는 프로그램을 작성해보자.

입력

첫째 줄에 정수 N (1≤N≤200000)과 K(1≤K≤100)가 주어진다.

둘째 줄에는 a1,a2,...an{a1, a2, ... an}이 주어진다 (1≤ai≤100000)

출력

조건을 만족하는 최장 연속 부분 수열의 길이를 출력한다.

노트

연속 부분 수열이란 그 수열의 원소를 하나 이상 연속하여 선택한 부분 수열을 말한다.

 a=3,9,7,6,5일 때 9,7,6는 연속 부분 수열이고 3,6,5는 그렇지 않다.

풀이

주어진 배열의 a[x] ~ a[y]까지 연속된 수의 집합에서, 안에 있는 원소들의 각각의 개수가 k개를 넘지 않는 수열을 찾는 문제이다.

a[x]~a[y]까지의 원소들의 각각 개수를 구하는 것은 count 배열을 만들어, 해당 원소의 빈도수를 저장해 주면 쉽게 구할 수 있다. 다만 2차원 for문으로 모든 x~y 구간에 대해 검사한다면 시간 초과가 뜰 것이니,

투 포인터란 알고리즘을 활용하자.

x를 start 포인트라고 두고,

y를 end 포인트라고 두었을 때,

a[0]부터 시작해서 end포인트를 a[1] a[2]로 점점 늘린다.

end포인트가 늘어나는 것은 수열의 길이가 점점 길어지는 것을 의미하며, 수열 안에 들어갈 원소들도 count에 빈도수를 저장해 주어야 한다.

만약 end포인트가 a[5]를 가리켜서 a[5]를 수열에 포함시켰는데 a[5]의 수가 k보다 많이 나왔다면, a[5]의 수가 k보다 적어질 때까지, start 포인트를 증가시키면서 기존에 start포인트가 가리키던 원소들을 수열에서 제외해 준다.  

end 포인트는 항상 증가하기 때문에, 본인은 그냥 입력받는 i 인덱스를 end포인트로 사용하였다.

 

코드1(c++)

#include <iostream>
#include <algorithm>
using namespace std;


//1<=n<=200000
//1<=k<=100
//같은 원소가 k개 이하로 들어있는 최장 연속 부분 수열 길이
int arr[200000];
int cnt[100001];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, k;
	cin >> n >> k;

	int answer = 0;
	int start=0;
	for (int i = 0; i < n; i++) {
		cin >>arr[i];
		cnt[arr[i]]++;
        //arr[i]를 수열에 포함시켰는데 arr[i]의 빈도수가 k보다 큰 경우 start 증가
		while(cnt[arr[i]] > k) {
			cnt[arr[start++]]--;
		}
		answer = max(answer, i-start+1);
	}
	cout << answer;

	return 0;
}

코드2(Kotlin)

val br = System.`in`.bufferedReader()

lateinit var arr: List<Int>
val visited = IntArray(100001)
fun main() = with(System.out.bufferedWriter()){

    //input
    val (n, k) = br.readLine().split(' ').map{it.toInt()}
    arr = br.readLine().split(' ').map{it.toInt()}
    //solve
    var answer=1
    var s=0
    for(e in 0 until n){
        while(visited[arr[e]]==k) {
            visited[arr[s++]]--
        }
        visited[arr[e]]++
        answer=  answer.coerceAtLeast(e-s+1)
    }
    //output
    write("$answer")
    close()
}