[백준 20922] 겹치는 건 싫어

문제

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

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

 

입력

첫째 줄에 N과 K를 입력하고

둘 째줄에는 N개의 숫자를 입력한다.

N은 1이상 200,000이하, K는 1이상 100이하이다.

 

출력

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

---

접근

투 포인터 알고리즘을 공부하기 위해 이 문제를 풀게되었다.

먼저 left와 right가 첫 번째 원소를 가리킨다. 

여기서 left가 가리키는 숫자가 K개 미만으로 나왔을 때 right를 증가시켜 범위를 확장한다.

그렇지 않을 때는 left를 증가시켜 범위를 좁힌다.

 

구현

- 입력받은 numbers 중에서 가장 큰 값에 해당하는 길이만큼 counter 리스트를 생성한다.

- counter를 통해 해당 숫자가 몇 번 나왔는지 체크한다.

- left와 right는 처음에 0을 가리키고

- right가 N 미만일 때까지 반복을 진행한다.

- 만약 left가 가리키는 숫자가 K번 미만으로 나왔다면 해당 숫자의 counter 리스트를 증가시키고 

- right를 증가시켜 범위를 확장한다.

- 그렇지 않을 때는 해당 숫자의 counter 리스트를 감소시키고 left를 증가시켜 범위를 좁힌다.

- 반복문 내내 right - left 로 최대 증가 부분 수열의 길이를 갱신한다.

N, K = map(int, input().split())
numbers = list(map(int, input().split()))
left, right = 0, 0

counter = [0] * (max(numbers) + 1)
answer = 0
while right < N:
    if counter[numbers[right]] < K:
        counter[numbers[right]] += 1
        right += 1
    else:
        counter[numbers[left]] -= 1
        left += 1
    answer = max(answer, right - left)
print(answer)