[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++ 코드

 

 

Kotlin 코드