백준 20922 겹치는 건 싫어 C++

백준 겹치는 건 싫어 20922 C++

문제 설명

문제

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

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

입력
첫째 줄에 정수 \(N\) (\(1 \le N \le 200{,}000\))과 \(K\) (\(1 \le K \le 100\))가 주어진다.

둘째 줄에는 \(\{a_1, a_2, \ldots, a_n\}\)이 주어진다 (\(1 \le a_i \le 100{,}000\)).

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

---

테스트케이스

예제 입력 1

9 2
3 2 5 5 6 4 4 5 7

예제 출력 1

7

예제 입력 2

10 1
1 2 3 4 5 6 6 7 8 9

예제 출력 2

6

---

문제 작동원리

이 문제의 핵심은 연속 부분 수열 안에서 모든 원소가 \(K\)번 이하로 등장해야 한다는 점입니다. 즉, 어떤 구간이 정답 후보가 되는지 아닌지를 구분하는 기준은 단 하나입니다.

• 정답 후보: 구간 안 모든 원소의 등장 횟수 \(\le K\)
• 정답 불가: 어떤 원소든 등장 횟수가 \(K+1\) 이상이면 조건 위반

이를 구체적인 사례로 살펴보겠습니다.

---

사례 1: 정답이 되는 구간

구간: \([3, 2, 5, 5, 6]\)

• 3 \(\to\) 1번
• 2 \(\to\) 1번
• 5 \(\to\) 2번
• 6 \(\to\) 1번

→ 모든 원소의 등장 횟수가 \(K=2\) 이하이므로 조건 만족, 정답 후보.

---

사례 2: 조건 위반 \(\to\) 정답 불가

구간: \([3, 2, 5, 5, 6, 4, 4, 5]\)

• 3 \(\to\) 1번
• 2 \(\to\) 1번
• 5 \(\to\) 3번
• 6 \(\to\) 1번
• 4 \(\to\) 2번

→ 5가 3번 등장해 \(K=2\)를 초과. 따라서 이 구간은 정답 후보에서 제외.

---

사례 3: 최장 길이 후보

구간: \([2, 5, 5, 6, 4, 4, 5]\)

• 2 \(\to\) 1번
• 5 \(\to\) 3번
• 6 \(\to\) 1번
• 4 \(\to\) 2번

→ 5가 3번 등장해 조건 위반.

하지만 start를 오른쪽으로 이동해 일부 원소를 제거하면:

구간: \([5, 6, 4, 4, 5]\)

• 5 \(\to\) 2번
• 6 \(\to\) 1번
• 4 \(\to\) 2번

→ 모든 원소의 등장 횟수가 \(K=2\) 이하, 조건 만족. 길이 = 5.

---

원리 정리

• end 전진: 조건이 만족되는 동안 구간을 확장해 최장 길이를 시도합니다.
• start 전진: 어떤 원소가 \(K+1\)번 이상 등장해 조건 위반이 되면, start를 옮겨서 조건이 다시 만족될 때까지 줄입니다.
• 최적 보장: end는 배열 전체를 순회하며 확장을 담당하고, start는 조건이 깨질 때만 이동합니다. 두 포인터가 모두 앞으로만 이동하므로 중복 없이 모든 경우를 다 살펴보게 되고, 그 과정에서 최장 길이를 얻을 수 있습니다.

결국, 투 포인터 방식은 이 문제의 조건을 자연스럽게 구현하면서 최적해를 보장하는 방법입니다.

---

아이디어의 원리

• end 전진 원리: 가능한 한 길게 구간을 확장해야 최장 부분 수열을 찾을 수 있습니다. 따라서 check[arr[end]] \(\le K\)일 때는 end를 계속 전진시킵니다.
• start 전진 원리: 만약 어떤 원소가 K개를 초과했다면 조건 위반이므로, start를 오른쪽으로 전진시키며 구간에서 원소를 빼줍니다. 조건이 만족될 때까지 계속합니다.
• 최적해 보장 원리: end는 전체 배열을 한 번 끝까지 훑으며 확장합니다. start는 조건이 깨질 때만 따라가서 회복합니다. 두 포인터 모두 한 번만 오른쪽으로 움직이므로 중복 없이 모든 경우를 확인하게 됩니다. 따라서 가능한 모든 연속 구간 후보를 빠짐없이 점검할 수 있고, 그 과정에서 최장 길이를 갱신하므로 최적해가 보장됩니다.

---

예제 시뮬레이션 (N=9, K=2, arr = 3 2 5 5 6 4 4 5 7)

---

초기 상태

arr:   3 2 5 5 6 4 4 5 7
start: ↑
end:   ↑

• 현재 구간 = `[3]`
• check[3] = 1 \(\to\) 1 \(\le 2\)
• 조건 만족 \(\to\) end 전진

---

step 1

arr:   3 2 5 5 6 4 4 5 7
start: ↑
end:     ↑

• 현재 구간 = `[3,2]`
• check[2] = 1 \(\to\) 조건 만족
• 길이 = 2
• end 전진

---

step 2

arr:   3 2 5 5 6 4 4 5 7
start: ↑
end:       ↑

• 현재 구간 = `[3,2,5]`
• check[5] = 1 \(\to\) 조건 만족
• 길이 = 3
• end 전진

---

step 3

arr:   3 2 5 5 6 4 4 5 7
start: ↑
end:         ↑

• 현재 구간 = `[3,2,5,5]`
• check[5] = 2 \(\to\) 조건 만족 (\(K=2\))
• 길이 = 4
• end 전진

---

step 4

arr:   3 2 5 5 6 4 4 5 7
start: ↑
end:           ↑

• 현재 구간 = `[3,2,5,5,6]`
• check[6] = 1 \(\to\) 조건 만족
• 길이 = 5
• end 전진

---

step 5

arr:   3 2 5 5 6 4 4 5 7
start: ↑
end:             ↑

• 현재 구간 = `[3,2,5,5,6,4]`
• check[4] = 1 \(\to\) 조건 만족
• 길이 = 6
• end 전진

---

step 6

arr:   3 2 5 5 6 4 4 5 7
start: ↑
end:               ↑

• 현재 구간 = `[3,2,5,5,6,4,4]`
• check[4] = 2 \(\to\) 조건 만족
• 길이 = 7
• end 전진

---

step 7 (조건 위반 발생)

arr:   3 2 5 5 6 4 4 5 7
start: ↑
end:                 ↑

• 현재 구간 = `[3,2,5,5,6,4,4,5]`
• check[5] = 3 \(\to\) 조건 위반 (\(K=2\) 초과)
• 따라서 start 전진하여 조건 회복 시도

---

step 7-1

arr:   3 2 5 5 6 4 4 5 7
start:   ↑
end:                 ↑

• 3 제거 \(\to\) check[3]=0
• 여전히 check[5]=3 \(\to\) 조건 위반

---

step 7-2

arr:   3 2 5 5 6 4 4 5 7
start:     ↑
end:                 ↑

• 2 제거 \(\to\) check[2]=0
• 여전히 check[5]=3 \(\to\) 조건 위반

---

step 7-3

arr:   3 2 5 5 6 4 4 5 7
start:       ↑
end:                 ↑

• 5 제거 \(\to\) check[5]=2
• 조건 만족 (\(K=2\))
• 현재 구간 = `[5,6,4,4,5]`
• end 전진

---

step 8

arr:   3 2 5 5 6 4 4 5 7
start:       ↑
end:                   ↑

• 현재 구간 = `[5,6,4,4,5,7]`
• check[7]=1, 하지만 check[5]=3 \(\to\) 조건 위반
• 따라서 start 전진

---

step 8-1

arr:   3 2 5 5 6 4 4 5 7
start:         ↑
end:                   ↑

• 5 제거 \(\to\) check[5]=2
• 조건 만족
• 현재 구간 = `[6,4,4,5,7]`

---

최종 결과

• 모든 과정을 거치면서 구한 최장 길이는 7입니다.
• 예시: [2,5,5,6,4,4,5] 또는 [5,5,6,4,4,5,7]

---

원리 요약

1. end 전진: 조건을 만족하는 동안 가능한 한 길게 구간을 확장합니다.
2. start 전진: 어떤 원소가 \(K\)개를 초과하면 조건이 깨지므로, start를 이동시켜 조건을 회복합니다.
3. 최적 보장: end는 배열 전체를 순회하며 확장을 담당하고, start는 조건 위반 시 최소한으로만 줄여 조건을 맞춥니다. 이 두 과정을 합치면 모든 연속 구간 후보가 빠짐없이 점검되고, 그중 최댓값을 얻을 수 있습니다.

---

전체 코드

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

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

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

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

    map<int, int> count;
    int start = 0;
    int max_len = 0;

    for (int end = 0; end < N; ++end) {
        count[arr[end]]++;

        while (count[arr[end]] > K) {
            count[arr[start]]--;
            start++;
        }

        max_len = max(max_len, end - start + 1);
    }

    cout << max_len << endl;

    return 0;
}

---

개별 코드

1. 입력 처리 및 자료구조 초기화

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

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

map<int, int> count;
int start = 0;
int max_len = 0;

• N, K를 입력받습니다.
• vector<int> arr에 수열을 저장합니다.
• map<int, int> count를 사용해 각 숫자의 빈도수를 효율적으로 관리합니다. (배열의 크기가 너무 커지므로 map이 더 적합합니다.)
• start는 투 포인터의 시작점, max_len은 최장 길이를 저장하는 변수입니다.

---

2. end 포인터 이동 (확장) 및 빈도수 체크

for (int end = 0; end < N; ++end) {
    count[arr[end]]++;

• end 포인터는 배열의 끝까지 반복하면서 한 칸씩 오른쪽으로 이동합니다.
• 새롭게 구간에 포함된 원소 arr[end]의 빈도수를 count 맵에 1 증가시킵니다.

---

3. 조건 위반 시 start 포인터 이동 (축소)

while (count[arr[end]] > K) {
    count[arr[start]]--;
    start++;
}

• 현재 end가 가리키는 원소의 빈도수가 K를 초과하면, 조건을 만족하지 않습니다.
• while 반복문을 통해 start 포인터를 오른쪽으로 한 칸씩 이동시킵니다.
• arr[start]의 빈도수를 1 감소시키고 start를 증가시킵니다.
• 이 과정은 빈도수 조건이 다시 만족될 때까지 계속됩니다.

---

4. 최대 길이 갱신

max_len = max(max_len, end - start + 1);

• 조건을 만족하는 현재 구간의 길이(end - start + 1)를 계산하여 max_len과 비교하고, 더 큰 값으로 갱신합니다.

---

5. 최종 출력

cout << max_len << endl;

• 모든 탐색이 끝난 후, max_len에 저장된 최장 길이를 출력합니다.

---

결론

이 문제는 투 포인터 + 빈도 체크 맵(또는 배열)을 이용해 \(O(N)\) 시간에 해결할 수 있습니다.

• 첫째, end 포인터는 항상 오른쪽으로 전진하면서 구간을 확장합니다.
• 둘째, 조건을 위반하면 start 포인터가 움직여서 구간을 줄입니다.
• 셋째, 각 숫자의 빈도를 map 또는 배열로 관리해 조건 위반 여부를 빠르게 판단합니다.
• 넷째, 이 과정을 통해 최장 연속 부분 수열 길이를 효율적으로 구할 수 있습니다.