백준 20922 - 파이썬

알고리즘 스터디를 하면서 어떤 문제를 풀지 고민하고 있었는데
같이 하는 형이 어떤 문제 풀고 싶은지 물어보길래
DFS,BFS,다이나믹 프로그래밍,... 등등 여러가지가 있었지만
'투 포인터'가 눈에 들어와서 이걸 풀어보자고 했다.
개념은 어디서 한 번 들어봤지만 문제를 풀어본 적은 없었기 때문이다.

문제

https://www.acmicpc.net/problem/20922
같은 원소가 $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$)

출력

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

풀이 아이디어

2개의 포인터를 사용해 부분 집합의 시작과 끝의 인덱스를 가리키고
만약 k개 이상의 중복된 숫자가 나온다면
시작 인덱스를 맨 처음 만나는 중복된 숫자의 인덱스를 찾고
그 다음 인덱스부터 다시 부분 집합을 센다.

풀이 코드

부분 수열의 시작 인덱스를 가리키는 포인터를 left
부분 수열의 끝 인덱스를 가리키는 포인터를 right라고 명명했다.

import sys
input = sys.stdin.readline

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

numbers = [0]*100002
length = 0
answer = 0
left=0
right=0
for num in array:
    numbers[num]+=1
    if(numbers[num]>k):
        answer = max(answer,right-left)

        # 겹치는 수를 찾을 때까지 left를 이동
        while(array[left]!=num):
            # 빠지는 인덱스의 경우의 수 값 빼기
            numbers[array[left]]-=1
            left+=1
            length-=1
        numbers[array[left]]-=1
        left+=1
        right+=1
    else:
        right+=1
        length+=1
answer=max(answer,right-left)
print(answer)