(Python/🥈2)백준리즘알고 20922번: 겹치는 건 싫어

 

문제 바로가기 

겹치는 건 싫어

 

문제:

홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열의 길이를 구하려고 한다.   100,000 이하의 양의 정수로 이루어진 길이가 N인 수열이 주어진다. 이 수열에서 같은 정수를 K개 이하로 포함한 최장 연속 부분 수열의 길이를 구하는 프로그램을 작성해보자.

입력:

첫째 줄에 정수 N ( 1 <= N <= 200,000)과 K ( 1 <= K <= 100)가 주어진다. 둘째 줄에는 {a1, a2, ... an}이 주어진다 

1<=ai <=100000

출력:

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

 

풀이:

import sys

sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

N, K = map(int,sys.stdin.readline().split(" "))
lst = list(map(int,sys.stdin.readline().split(" ")))

count = [0] * 100001
left, right = 0,0
res = 0

while right < N:
    if count[lst[right]] < K:
        count[lst[right]] +=1
        right +=1
    else:
        count[lst[left]] -= 1
        left += 1
    res = max(res, right-left)
print(res)

 

처음에는 counter함수나, 딕셔너리를 사용하려했지만 K와 비교하는것땜에 포기하였고 기본 투포인터를 사용했다.

둘다 시작점은 0,0 이고 오른쪽으로 하나씩 가면서 K개보다 넘어가는순간 left를 옮긴다.

그러다 오른쪽이 N보다 커지면 끝난다.

 

잘 모르겠다면

https://khu98.tistory.com/187

[백준OJ] 20922번 겹치는 건 싫어

이분 블로그에서 그림을 보면 될것같다.