[백준] 20922 - 겹치는 건 싫어 python 투포인터

- 난이도 : 실버 1

- 시간제한 : 1초 (추가 시간 없음)

- 메모리 제한 : 1024MB

 

문제

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

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

 

입력

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

둘째 줄에는 a1, a2, ... , an이 주어진다. (1<= ai <=100,000)

 

출력

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

 

---

가장 처음에 생각했던 방식은 

입력된 a 리스트의 첫 값부터 반복문을 돌면서 중복 값이 없는지 확인하며 길이를 세는 방식이었다.

 

너무 간단하게 생각했더니 도무지 어떻게 구현해야 할 지 감이 안왔다..

 

[백준 20922번] 파이썬 - 겹치는 건 싫어

 

위 블로그를 참고해서 풀어보았다.

 

이 문제에서는 투포인터 알고리즘을 사용한다.

투포인터(Two Pointer) 란 ?

• 리스트에 순차적으로 접근해야 할 때, 두 개의 점의 위치를 기록하면서 처리하는 알고리즘
• 정렬되어 있는 두 리스트의 합집합에도 사용됨. 병합정렬(merge sort)의 counquer 영역의 기초가 되기도 함
• 슬라이딩 윈도우(Sliding Window)라고도 부른다 !

 

전에도 슬라이딩 윈도우를 사용하는 문제를 풀었는데 여기에 적용할 생각은 못했다... 

어케 생각하는거지 ????

 

암튼 적용해서 풀어보면 다음과 같은 방식을 따른다.

• 원소 개수를 저장할 리스트를 하나 만듦
• start, end 포인터를 0 위치에 둠
• end 위치를 한 칸씩 뒤로 가면서 원소 개수 세기
• 만약 K개 이상이 된다 ? 그러면 left를 한 칸 이동하고 counter에서 left가 있던 위치의 원소 개수를 한 개 빼준다
• end - start 값이 최대일 때를 출력해주면 됨 !

from sys import stdin as s

n, k = map(int, s.readline().strip().split())
arr = list(map(int, s.readline().strip().split()))
cnt = [0] * (max(arr) + 1)

start, end, res = 0, 0, 0

while end < n:
    if cnt[arr[end]] < k:
        cnt[arr[end]] += 1
        end += 1
    else:
        cnt[arr[start]] -=1
        start += 1
    res = max(res, end-start)

print(res)