[Python | 20922] 겹치는 건 싫어

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

---

문제 설명

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

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

 

📌 시간 제한: 1초

---

입력

첫째 줄에 정수 N(1≤N≤200000)과 K(1≤K≤100)가 주어진다.

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

---

출력

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

---

문제 접근

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

---

구현

이 문제는 주어진 수열에서 어떤 수가 K번을 초과해서 등장하지 않도록 하면서, 그 안에서 만들 수 있는 가장 긴 연속 부분 수열을 찾는 문제이다.

 

처음 문제를 보면 단순히 모든 부분 수열을 검사해서 조건을 확인하고 길이를 비교하고 싶을 수 있다. 하지만 수열의 길이 N이 최대 200,000이기 때문에, 완전 탐색(O(N²))은 시간 초과가 발생한다.

 

게다가, "가장 긴 연속 부분 수열"이라는 표현에서 우리는 연속된 구간을 다루어야 함을 알 수 있고, 여기에 "같은 수가 K번을 초과하지 않도록"이라는 제약 조건이 추가되면서, 조건을 만족하는 구간을 효율적으로 탐색해야 한다는 사실을 떠올릴 수 있다.

이처럼 조건을 만족하는 구간을 유지하면서, 그 길이를 최적화해야 하는 문제는 투 포인터 기법이 특히 유효하게 작동한다.
따라서 이 문제는 투 포인터(two pointer) 기법을 사용해 푸는 것이 적절하다.

 

우리는 두 개의 포인터(left, right)를 사용해서 다음과 같은 방식으로 윈도우를 유지한다:

1. 오른쪽 포인터(right)를 하나씩 이동하며 윈도우에 새로운 숫자를 추가한다.
2. 만약 어떤 숫자가 윈도우 내에서 K번을 초과해서 등장한다면, 왼쪽 포인터(left)를 오른쪽으로 옮겨 그 숫자의 개수를 줄인다.
3. 위 과정을 반복하면서 항상 윈도우가 유효할 때마다 그 길이를 계산하고, 최댓값을 저장한다.

이 과정은 각 숫자가 정확히 한 번씩 추가되고 한 번씩 제거되기 때문에, 총 시간복잡도는 O(N)이다.

---

구현

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
nums = list(map(int, input().split()))

cnt = [0] * 100001  # 숫자별 등장 횟수
left = 0
max_len = 0

for right in range(n):
    cnt[nums[right]] += 1

    while cnt[nums[right]] > k:
        cnt[nums[left]] -= 1
        left += 1

    max_len = max(max_len, right - left + 1)

print(max_len)