백준 20922: 겹치는 건 싫어 - 투 포인터(파이썬)

겹치는 건 싫어 성공

20922번: 겹치는 건 싫어

문제

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

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

입력

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

둘째 줄에는 {a_1, a_2, ... a_n}이 주어진다 (1≤a_i≤100000)

출력

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

 

내 코드

import sys
n,k=map(int,sys.stdin.readline().split())
num=list(map(int,sys.stdin.readline().split()))

#각 수의 개수를 저장할 cnt[]. 개수는 가장 큰 수+1해서 바로 수로 인덱스 접근 가능하게.
cnt=[0 for _ in range(max(num)+1)]

start,end=0,-1 #while문 처음에 end++가 있어서 end=-1 초기화.
lengthList=[] #각 요소를 포함할 때의 최대 길이를 저장할 것임.

#각 요소별 최대 길이를 저장하면 while 종료.
while len(lengthList)!=n:
    if end<n-1: #end는 수의 개수-1 까지만 가능.
        end+=1

    cnt[num[end]]+=1 #end가 가리키는 숫자의 cnt++;

    while cnt[num[end]]>k: #그 cnt가 k보다 크면, 작아질 때까지 start를 전진.
        cnt[num[start]]-=1 #start를 전진하기 전에 먼저 start의 수의 cnt를 -1 해주고,
        start+=1 #start 전진.
    
    length=(end-start)+1 #그 때의 길이는 (end-start)+1
    lengthList.append(length) #lengthList에 이 길이를 저장.

#저장한 길이 값 중 최대가 정답
print(max(lengthList))

풀이 및 접근)

- 이 문제는 투 포인터를 이용한 문제이다.

- 처음에는 누적 합의 아이디어로 i번째 에서의 최대는 조건을 만족하면 [i-1]번째의 길이+1, 조건을 만족하지 못하면 1로 초기화 하는 식으로 접근했었다. 하지만 이는 잘못된 풀이인게, 특정 순간 조건을 위배했다 하더라도 그 시점에서 초기화 시키는 것이 아니라 구간의 길이를 좁히면 초기화를 시키지 않고도 더 큰 값을 얻어 낼 수 있다.

- 이러한 한계를 깨닫고, 구간의 길이를 유동적으로 바꿀 수 있는 투 포인터를 생각해냈다.

- 시작점, 끝점을 0,0에서 시작해서 끝점을 전진시켜 나간다. 그러면서 그 길이를 배열에 저장한다. 그러다가 조건을 위배하면, 조건을 다시 만족할 때까지 start를 전진 시키면서 구간을 좁힌다. 그러다가 만족하는 순간일 때가 최대이므로 그 순간의 길이를 저장한다.

- 모든 요소별 길이가 저장되었으면 while문을 탈출한다. 그러면 이 때 lengthList에 요소의 개수만큼 길이가 저장되어 있다. 특정 요소가 제일 끝 지점일 때의 최대 길이들이 저장되어 있다.

- 이들 중에 최대값이 답이 된다.