[백준, C++] 20922 - 겹치는 건 싫어

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

20922번: 겹치는 건 싫어

 

문제 분석

크기가 N인 어떤 수열이 주어진다. 이 수열의 연속 부분 수열 중 가장 긴 연속 부분 수열의 길이를 구할 것인데, 연속 부분 수열의 조건은 연속 부분 수열을 이루는 숫자 중 같은 숫자가 중복해서 나와도 되지만 K개 이하로 나와야 한다는 것이다.

 

N은 최대 20만이다. 따라서 완전 탐색으로 접근 시 O(N^2)이 소요되므로 시간 초과가 날 가능성이 있다. 따라서 이를 최대한 줄여야 한다.

 

옛날에 투 포인터 라는 문제 해결 방법을 배운 적이 있다. 이는 특히 부분 수열 관련된 문제들 중, O(N^2)이 걸리는 풀이를 O(2 * N), 즉 O(N)으로 줄일 수 있는 방식이다. 이 문제를 투 포인터와 비슷한(사실은 동일한) 방법으로 풀면 될 것이라고 생각했다. 이게 가능한 이유는 문제에서 찾고자 하는 부분 수열이 연속 부분 수열이기 때문에 가능하다.

 

코드

#include <iostream>

using namespace std;

int n, k;
int arr[200000];
int counter[100001];
int result;

void getInput() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
}

void solve() {
    int startIndex = 0;
    for (int i = 0; i < n; i++) {
        counter[arr[i]]++;
        while (counter[arr[i]] > k) {
            counter[arr[startIndex]]--;
            startIndex++;
        }

        result = max(result, i + 1 - startIndex);
    }
}

void printResult() {
    cout << result << "\n";
}

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    getInput();
    solve();
    printResult();
}

 

코드 설명

사실 입력을 받는 부분과 문제를 푸는 부분(getInput()과 solve())을 통합하여 풀 수 있긴 하다. 입력을 받는 메서드 안의 for문과 문제를 푸는 메서드 안의 for문이 0부터 N - 1까지를 순회하기 때문이다. 문제의 풀이 방식은, 현재 읽고 있는 인덱스(i)의 값에 대한 카운트를 증가시키면서, 증가시켰을 때 카운트가 K를 초과한다면 연속 부분 수열의 startIndex 부분부터(앞부분부터) 잘라내는 방식이다.

 

투 포인터로 풀면 되겠다고 생각은 했는데, 막상 코드를 작성하는 데까지 매우 오랜 시간이 걸렸다. 1시간 정도 고민했나 . . . 쉽지 않은 여정이었다.