블로그
[백준] 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 리스트의 첫 값부터 반복문을 돌면서 중복 값이 없는지 확인하며 길이를 세는 방식이었다.
너무 간단하게 생각했더니 도무지 어떻게 구현해야 할 지 감이 안왔다..
위 블로그를 참고해서 풀어보았다.
이 문제에서는 투포인터 알고리즘을 사용한다.
투포인터(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)
728x90
반응형
'공부 > 알고리즘' 카테고리의 다른 글
[알고리즘] 최소 신장 트리(MST), 크루스칼 알고리즘(Kruskal Algorithm) (0) | 2024.03.22 |
---|