[백준][최장연속부분수열][투포인터] 20922. 겹치는 건 싫어

20922. 겹치는 건 싫어

20922번: 겹치는 건 싫어

최장 연속 부분 수열(Longest Continuous Subsequence)

* 연속부분수열: 그 수열의 원소를 하나 이상 연속하여 선택한 부분수열 (수가 연속적일 필요는 없음)

일련의 숫자 또는 요소로 이루어진 배열에서, 순서를 유지하며 가장 긴 연속 부분 수열을 찾는 문제

배열 내에서 순서가 중요하며, 다른 요소들이 끊김 없이 연속

ex) [1, 2, 3, 5, 1, 2, 3, 4]인 경우, 최장 연속 부분 수열은 [1, 2, 3, 4]

 

• 다른 사람 풀이
  • 투포인터 사용
  • 앞에서 구한 배열로 길이 저장해두면서 최댓값이 될때 업데이트 되도록
  • k개가 넘지 않을 때는 +1
  • k개가 넘으면 앞의 배열 제외하고 뒤를 늘려나가면서 길이 비교

from collections import defaultdict
# 같은 원소가 k개 이하인 최장 연속 부분 수열 길이
n, k = map(int, input().split())
lst = list(map(int, input().split()))
count = defaultdict(int)

ans = 0
left, right = 0, 0
while right < n:
    if count[lst[right]] < k:
        count[lst[right]] += 1
        right += 1
    else:
        count[lst[left]] -= 1
        left += 1
    ans = max(ans, right-left)

print(ans)