[BOJ] 20922번 - 겹치는 건 싫어

오늘 풀어본 문제는 [BOJ] 20922번 - 겹치는 건 싫어 입니다.

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

20922번: 겹치는 건 싫어

 

알고리즘

---

위 문제는 연속되는 부분 수열 중에서 특정 숫자가 K개 아래인 경우 중 제일 긴 길이를 선택하면 됩니다.

N의 범위는 10만 a의 범위는 10만으로써, 메모리가 1024MB임으로 여유가 있으니 해당 범위만큼 길이를 선언하고 시작해도 무방할 것으로 보입니다.

한번만 순회하면서 가장 긴 경우의 수를 찾기 위해 투포인터라는 알고리즘을 사용하였습니다.

List를 하나씩 순회하면서 갈 수 있는 최대 경우의 수를 Right라고 하며, 계속하여 갱신해줍니다.

 

코드

---

#BOJ 20922번

import sys
input = sys.stdin.readline 

n , k = map(int,input().split())
datas = list(map(int,input().split()))
a = [0]*100001

right , answer = 0 , 0

for i in range(n) :
    while right < n and a[datas[right]] < k :
        answer = max(answer,right-i+1)
        a[datas[right]] += 1
        right += 1

    a[datas[i]] -= 1
    
print(answer)