겹치는 건 싫어 성공
시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) | 1024 MB | 9838 | 3568 | 2732 | 35.425% |
문제
홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 � 개 이하로 들어 있는 최장 연속 부분 수열의 길이를 구하려고 한다.
100000 � 인 수열이 주어진다. 이 수열에서 같은 정수를 � 개 이하로 포함한 최장 연속 부분 수열의 길이를 구하는 프로그램을 작성해보자.
이하의 양의 정수로 이루어진 길이가입력
첫째 줄에 정수 � (1≤�≤200000 )과 � (1≤�≤100 )가 주어진다.
둘째 줄에는 �1,�2,...�� 이 주어진다 (1≤��≤100000 )
출력
조건을 만족하는 최장 연속 부분 수열의 길이를 출력한다.
예제 입력 1 복사
9 2
3 2 5 5 6 4 4 5 7
예제 출력 1 복사
7
문제 풀이
같은 원소의 개수를 확인하면서 탐색해야한다.
=> 수열의 같은 원소 개수를 담기 위한 counter[] 생성한다.
만약 counter[수열원소값] < k 인 경우
값을 더하고, 이동한다.
아닌 경우
수열의 처음 부분을 앞으로 당기고
그 수열의 처음부분의 원소 개수 값을 뺀다.
이 때 만들어진 부분수열의 길이를 answer와 비교해 max값을 넣는다.
n, k = map(int, input().split())
numbers = list(map(int, input().split()))
left, right = 0, 0
# 이걸 왜 하는걸까
counter = [0] * (max(numbers) + 1)
answer = 0
while right < n:
if counter[numbers[right]] < k:
counter[numbers[right]] += 1
right += 1
else:
counter[numbers[left]] -= 1
left += 1
answer = max(answer, right - left)
print(answer)
'programming language > Algorithm' 카테고리의 다른 글
[백준] 11660 구간 합 구하기 5 python (0) | 2024.02.14 |
---|---|
Two Pointer 개념 정리 (0) | 2024.02.07 |
[이코테] 음료수 얼려먹기 python (0) | 2024.02.02 |
[백준] 13549 숨바꼭질3 python (0) | 2024.02.02 |
[백준] 17836 공주님을 구해라! python (0) | 2024.02.02 |