백준 BOJ 20922번 : 겹치는 건 싫어 (투 포인터 알고리즘)

날마다 아무거나 골라서 풀고 있는데 어쩌다보니 또 다시 투 포인터(two pointer) 알고리즘 문제를 풀게 되었습니다.

문제가 나쁘지는 않은 것 같아 가지고 와봤습니다.

 

 

백준 BOJ 20922 : 겹치는 건 싫어

길이 N의 수열과 정수 K가 주어질 때, 이 수열에서 같은 정수를 K개 이하로 포함한 연속 부분 수열들 중 가장 긴 것의 길이를 출력하는 문제입니다.

시작점과 끝점의 위치를 각각의 변수로 놓고 생각하면 N * (N-1) / 2개의 경우의 수를 모두 해보면 좋겠지만, 이는 O(N^2) 알고리즘이므로 시간 초과가 발생하게 됩니다.

따라서 다음과 같이 투 포인터 알고리즘을 사용하여 구간을 탐색하는 것이 바람직합니다.

 

 

 

문제에서 주어진 예제 입력으로 알고리즘을 설명하자면, i와 j를 모두 시작점에 놓고 이동시킵니다.

j는 같은 숫자가 K개 이상 나오는 구간이 될 때까지 증가시켜줍니다.

만약 같은 숫자가 K개보다 많이 나온다면 이제 j를 멈추고 i를 증가시키면서 같은 숫자가 K개 이하가 될 때까지 구간의 길이를 줄여줍니다.

이런 식으로 반복하면서 j가 수열의 끝까지 이동할 때까지 답을 갱신해주고, 탐색이 끝난 이후 지금까지 나왔던 수열들의 길이 중에서 가장 길이가 긴 것의 길이를 출력해주면 됩니다.

 

이제 위의 알고리즘을 소스 코드로 구현해보도록 하겠습니다.

 

 

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, K; cin >> N >> K;

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

    int cnt[200001] = {}, ans = 0;
    int i=0, j=0;

    while(true) {
        if(i > j || j >= N) break;

        if(cnt[arr[j]] < K) {
            cnt[arr[j]]++;
            j++;
            ans = max(ans, j-i);
        }
        else if(cnt[arr[j]] == K) {
            cnt[arr[i]]--;
            i++;
        }
    }

    cout << ans;
}

 

위와 같이 i가 j를 역전하거나 j가 끝에 도달하면 break를 걸어주도록 하고, 그 외의 경우에는 무한루프를 돌며 cnt 배열에 각 숫자의 개수를 count해줍니다.

문제에서 수열의 각 항은 10만 이하라고 하였으므로 배열 크기를 최소 10만 이상으로 잡아 count 해줄 수 있도록 합니다.

 

나머지 구현은 위에서 설명한 것과 동일합니다.

j가 오른쪽으로 이동할 때만이 최장 수열의 길이가 갱신될 가능성이 있는 것이므로 ans = max(ans, j-i)로 답을 조건부 갱신해주면 됩니다.