[백준] 20922_겹치는 건 싫어 (투 포인터 이용)

📕 백준

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

20922번: 겹치는 건 싫어

 

💡 풀이법

: 연속 부분 수열의 길이를 구하는 문제이기 때문에 바로 투 포인터를 떠올렸다.

 

1. 먼저 숫자들의 개수를 담을 count 딕셔너리를 만들어줬다.

2. left와 right 포인트를 0으로 두고, 문자열의 길이를 l, 최장 연속 부분 수열의 길이를 담는 변수를 ans라고 두었다.

3. left가 right보다 작고, right가 수열보다 작으면 while문을 실행한다.

4. 진행하는 동안 선택되는 수열은 lst[left:right]이다.

5. 먼저 right 포인터가 가르키는 수가 현재 문자열에서 K보다 적게 들어 있다면 그 숫자를 문자열에 포함시켜준다.

(즉, 숫자의 개수를 1 증가시키고, right 포인터를 1 증가시켜 주고, l도 1 증가 시켜준다.)

6. 만약 right 포인터가 가르키는 수를 더 이상 넣을 수 없다면 문자열의 맨 앞의 숫자를 빼준다.

(즉, 맨 앞의 숫자의 개수를 -1 해주고, left 포인터를 1 증가시키고, l도 1 감소 시킨다.)

7. 실행하는 동안 계속 l을 ans와 비교해주며 l이 더 크다면 ans를 l로 바꾼다.

8. while문이 끝나면 한번 더 l을 ans와 비교해서 l이 더 크다면 ans를 바꿔준다.

 

from collections import defaultdict

def two_pointer(lst):
    ans, l = 0
    left = right = 0

    while left <= right and right < len(lst):

        if l > ans:
            ans = l

        if count[nums[right]] < K:
            right += 1
            count[nums[right-1]] += 1
            l += 1
        else:
            count[nums[left]] -= 1
            left += 1
            l -= 1
    
    if l > ans:
        ans = l

    return ans

N, K = map(int, input().split())
nums = list(map(int, input().split()))
count = defaultdict(int)
print(two_pointer(nums))