-
[BOJ] 20922번 - 겹치는 건 싫어Algorithm/BOJ 2022. 6. 29. 12:16
오늘 풀어본 문제는 [BOJ] 20922번 - 겹치는 건 싫어 입니다.
https://www.acmicpc.net/problem/20922
20922번: 겹치는 건 싫어
홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열
www.acmicpc.net
알고리즘
위 문제는 연속되는 부분 수열 중에서 특정 숫자가 K개 아래인 경우 중 제일 긴 길이를 선택하면 됩니다.
N의 범위는 10만 a의 범위는 10만으로써, 메모리가 1024MB임으로 여유가 있으니 해당 범위만큼 길이를 선언하고 시작해도 무방할 것으로 보입니다.
한번만 순회하면서 가장 긴 경우의 수를 찾기 위해 투포인터라는 알고리즘을 사용하였습니다.
List를 하나씩 순회하면서 갈 수 있는 최대 경우의 수를 Right라고 하며, 계속하여 갱신해줍니다.
코드
#BOJ 20922번 import sys input = sys.stdin.readline n , k = map(int,input().split()) datas = list(map(int,input().split())) a = [0]*100001 right , answer = 0 , 0 for i in range(n) : while right < n and a[datas[right]] < k : answer = max(answer,right-i+1) a[datas[right]] += 1 right += 1 a[datas[i]] -= 1 print(answer)
'Algorithm > BOJ' 카테고리의 다른 글
[BOJ] 2283번 - 구간 자르기 (0) 2022.07.06 [BOJ] 2461번 - 대표 선수 (0) 2022.07.05 [BOJ] 13144번 - List of Unique Numbers (0) 2022.06.22 [BOJ] 2110번 - 공유기 설치 (0) 2022.06.20 [BOJ] 8980번 - 택배 (0) 2022.06.20