[백준/투 포인터] - 겹치는 건 싫어

문제 링크

코드

from collections import defaultdict

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

c = defaultdict(int) # 정수 개수 카운트

l, r = 0, 0 # 투 포인터
_max = 0 # 최장 연속 부분 수열의 길이

while l <= r and r < len(_list):
    if c[_list[r]] < k: # k개 미만으로 등장한 경우
        c[_list[r]] += 1 # 카운트 증가
        r += 1 # 포인터 이동
    else: # k개 이상으로 등장한 경우
        c[_list[l]] -= 1 # 카운트 감소
        l += 1 # 포인터 이동
    _max = max(_max, r - l) # 길이 갱신

print(_max)

풀이

문제의 목표

• 같은 원소가 K개 이하로 포함되는 최장 연속 부분 수열의 길이 구하기

먼저 포인터를 이동시키면서 방문한 원소의 카운트 값을 1 증가 시킨다. 이때, 같은 정수가 K개 미만일 경우에만 증가시킨다.

왜 K개 이하가 아닌가?

문제의 조건에서는 K개 이하라고 명시되어있다.

예를 들어, 1 2 3 4 5 6 6 7 8 9, k = 1라고 해보자.

만약, if c[_list[r]] <= k: 라면 r은 인덱스 7(원소: 7)에 위치하게 되고, 이때 수열의 길이는 7(r - l = 7)이된다. 즉, 중복되는 원소 6이 2개가 포함된 경우의 길이로 갱신된다.

이러한 경우를 배제시키기 위해 K개 미만으로 설정해야 한다.

그리고, 최장 연속 부분 수열의 길이는 매 탐색마다 확인해서 갱신한다.