백준 20922 겹치는 건 싫어 파이썬 (python)

백준 겹치는 건 싫어 20922 파이썬

문제 설명

문제

홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 \(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는 조건 위반 시 최소한으로만 줄여 조건을 맞춥니다. 이 두 과정을 합치면 모든 연속 구간 후보가 빠짐없이 점검되고, 그중 최댓값을 얻을 수 있습니다.

---

전체 코드

N, K = map(int, input().split())

arr = list(map(int, input().split()))
check = [0] * 100001
start = 0
end = 0
max_cnt = 0

while end < N:
    check[arr[end]] += 1

    while check[arr[end]] > K:
        check[arr[start]] -= 1
        start += 1

    max_cnt = max(max_cnt, end - start + 1)
    end += 1

print(max_cnt)

---

개별 코드

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

N, K = map(int, input().split())
arr = list(map(int, input().split()))
check = [0] * 100001
start = 0
end = 0
max_cnt = 0

• N, K를 입력받습니다.
• arr 리스트에 수열을 저장합니다.
• check 리스트는 각 숫자의 빈도수를 세기 위한 용도입니다. 문제의 값 범위에 맞춰 크기 100,001로 초기화합니다.
• start와 end는 투 포인터의 시작점, max_cnt는 최장 길이를 저장하는 변수입니다.

---

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

while end < N:
    check[arr[end]] += 1

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

---

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

while check[arr[end]] > K:
    check[arr[start]] -= 1
    start += 1

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

---

4. 최대 길이 갱신

max_cnt = max(max_cnt, end - start + 1)

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

---

5. end 포인터 전진 및 최종 출력

end += 1

print(max_cnt)

• 현재 단계가 끝나면 end를 전진시켜 다음 탐색을 준비합니다.
• 모든 탐색이 끝난 후, max_cnt에 저장된 최장 길이를 출력합니다.

---

결론

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

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