20922번 겹치는 건 싫어

📌Problem

홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열의 길이를 구하려고 한다.

 $100\,000$ 이하의 양의 정수로 이루어진 길이가 $N$인 수열이 주어진다. 이 수열에서 같은 정수를 $K$개 이하로 포함한 최장 연속 부분 수열의 길이를 구하는 프로그램을 작성해보자.

입력

첫째 줄에 정수 $N$ ($1 \le N \le 200\,000$)과 $K$ ($1 \le K \le 100$)가 주어진다.

둘째 줄에는 ${a_1, a_2, ... a_n}$이 주어진다 ($1 \le a_i \le 100\,000$)

출력

조건을 만족하는 최장 연속 부분 수열의 길이를 출력한다.

✍solution

(two point 알고리즘)
1. 배열을 순회하는 시작점과 끝점을 정하기
2. 끝점을 이동하면서 해당 원소의 개수를 체크
3. 해당 원소가 최대 개수보다 많아지는 경우 시작점을 이동하며 원소의 개수는 제외 시키기
4. 길이는 원소를 제외시키기 전의 길이가 됨
5. 이런 식으로 포인트를 이동하며 최대 길이를 구하기
6. 끝점이 배열의 마지막 원소의 개수를 체크했을 때 순회 종료

💻Code

check_arr = [0]*100001
s=0
e=0
n,k = map(int, input().split())
arr = list(map(int, input().split()))

max_len = 0
while True:
    if e == n:
        max_len = max(max_len, e - s)
        break
    if check_arr[arr[e]] == k:
        check_arr[arr[s]]-=1
        max_len = max(max_len, e-s)
        s += 1
    else:
        check_arr[arr[e]]+=1
        e += 1
print(max_len)

💡Takeaway

• 끝점이 배열의 마지막 값을 넣었을때 최대 길이를 한번 더 체크