백준 #20922 - [S1] 겹치는 건 싫어 : 두포인터

(python3)

20922번: 겹치는 건 싫어

 

 

두  포인터로 시작점과 끝점 잡기, 원소별 등장 횟수 세기

원소별로 등장 횟수를 세면서 횟수가 K가 넘어갈때까지 끝점을 한칸씩 뒤로 옮깁니다.

등장 횟수 카운팅은 try except와 dict를 활용했습니다.

카운팅이 K를 넘어간 경우 s ~ e-1 의 문자열 길이를 확인해서 최대 부분 문자열 길이를 찾습니다.

마지막에 추가되면서 임계치를 넘긴 그 문자가 나올때까지 s를 뒤로 밉니다.

s를 밀면서 s~e 에서 빠지는 문자들의 카운팅도 빼줍니다.

타겟 문자를 찾았으면 타겟 문자까지 제외시킵니다.

이 과정을 e가 끝에 도달할때까지 반복해줍니다.

(실수 메모 : max len 구하는걸 K가 넘어가는 순간에만 계산해줬기 때문에 위 반복문이 끝나고 나서도 계산해줘야합니다!)

 

코드

import sys
def solution(input) :
    N,K = list(map(int,input().split()))
    L = list(map(int,input().split()))
    D = {}
    s = 0
    e = 0
    maxlen = 0
    while e < N : # e가 끝까지 갈때까지 반복
        try :
            D[L[e]] += 1
            if D[L[e]] > K :
                maxlen = max(maxlen, e-s)
                while L[s] != L[e] : # s 뒤로 밀기
                    D[L[s]] -= 1
                    s+=1
                D[L[s]] -= 1
                s+=1
               
        except :
            D[L[e]] = 1 # 처음 들어가는 원소 에러 처리
        e+=1
    maxlen = max(maxlen, e-s)
    
    print(maxlen)

        
input = sys.stdin.readline
solution(input)

 

my solved.ac :

solved.ac