[BOJ] 20922 겹치는 건 싫어 바로가기
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초 (추가 시간 없음) 1024 MB 4255 1436 1086 33.769%
문제
홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 개 이하로 들어 있는 최장 연속 부분 수열의 길이를 구하려고 한다.
이하의 양의 정수로 이루어진 길이가 인 수열이 주어진다. 이 수열에서 같은 정수를 개 이하로 포함한 최장 연속 부분 수열의 길이를 구하는 프로그램을 작성해보자.
첫째 줄에 정수 ()과 ()가 주어진다.
둘째 줄에는 이 주어진다 ()
조건을 만족하는 최장 연속 부분 수열의 길이를 출력한다.
while end < N:
if numberCount[A[end]] >= K:
numberCount[A[start]] -= 1
start += 1
else:
numberCount[A[end]] += 1
end += 1
answer = max(answer, end - start)
start
, end
변수의 초기값은 0
으로 초기화 한다.start
인덱스부터 end
인덱스까지 해당하는 부분 수열이 K
개 이상의 중복이 없는지 검사한다.end
의 값을 증가시키면서 end
인덱스에 해당하는 숫자의 개수를 증가시킨다.end
인덱스에 해당하는 숫자의 개수가 K
를 넘는다면 end
의 진행은 중단시키고 start
의 값을 증가시키면서 start
인덱스에 해당하는 숫자의 개수를 감소시킨다.start
의 값을 증가하는 중 end
인덱스에 해당하는 숫자의 개수가 K
와 같아진다면 다시 end
의 값을 증가시키는 연산을 반복한다.from sys import stdin
from collections import defaultdict
def solution(N, K, A):
answer = 0
start, end = 0, 0
# [1] 수열에 주어진 각 정수의 개수
numberCount = defaultdict(int)
# [2] 투 포인터
while end < N:
if numberCount[A[end]] >= K:
numberCount[A[start]] -= 1
start += 1
else:
numberCount[A[end]] += 1
end += 1
answer = max(answer, end - start)
return answer
# input
N, K = map(int,stdin.readline().split())
A = list(map(int,stdin.readline().split()))
# result
result = solution(N, K, A)
print(result)