(백준 알고리즘 문제풀이) 20922번 겹치는 건 싫어

문제

문제 링크

 

문제 접근

• a에 들어갈 수 있는 범위 (1 <= a <= 100,000)이기때문에 count를 100,001개의 리스트 생성
• a리스트에 들어가 있는 수의 칸에 있는 카운트 증가시키기
• a[i]를 포함 시켰을 때, 제한된 크기인 k보다 클 경우에 처음 나왔던 a[i]와 동일한 수 까지 빼주기
• 최장 부분 수열의 최대 개수를 출력

코드

import sys
input = sys.stdin.readline

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

count = [0] * 100001
start, result = 0, 0

for i in range(n):
    count[a[i]] += 1
    # a[i]를 포함 시켰을 때, 제한된 크기인 k보다 클 경우에 처음 나왔던 a[i]와 동일한 수 까지 빼주기
    while count[a[i]] > k:
        count[a[start]] -= 1
        start += 1
    # 최장 부분 수열의 개수가 큰 것을 고르는 과정
    result = max(result, i - start + 1)

# 결과 출력
print(result)