문제
홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 𝐾개 이하로 들어 있는 최장 연속 부분 수열의 길이를 구하려고 한다.
100,000 이하의 양의 정수로 이루어진 길이가 𝑁인 수열이 주어진다. 이 수열에서 같은 정수를 𝐾개 이하로 포함한 최장 연속 부분 수열의 길이를 구하는 프로그램을 작성해보자.
입력
첫째 줄에 정수 𝑁(1≤𝑁≤200,000)과 𝐾 (1≤𝐾≤100)가 주어진다.
둘째 줄에는 𝑎1,𝑎2,...𝑎𝑛{a_1, a_2, ... a_n}이 주어진다 (1≤𝑎𝑖≤100000)
출력
조건을 만족하는 최장 연속 부분 수열의 길이를 출력한다.
예제 입력 1
9 2
3 2 5 5 6 4 4 5 7
예제 출력 1
7
예제 입력 2
10 1
1 2 3 4 5 6 6 7 8 9
예제 출력 2
6
아이디어
먼저, 예제 두 가지를 살펴보았다.
two-pointer를 구현하기 위해서 start,end 를 각각의 포인터로 잡는다.
그런데, 만약에 K+1개 이상 있는 수가 여러개라면? 여러 가지의 수열이 나오지 않을까?
따라서 이러한 반례도 작성해보았다.
이렇게 3가지, 4가지, … 여러가지 수열이 나올 수도 있음을 함께 고려해주어야 한다.
문제 풀이
'''
백준 20922번
겹치는 건 싫어
'''
n , k = map(int,input().split() )# n = 수열의 길이, # k = 최장 연속 부분 수열에서 포함될 수 있는 같은 정수의 최대 개수
seq = list(map(int, input().split())) # 수열
# sequence에 대해 원소 별 개수를 세서 K+1 개 이상인 원소를 반환하는 함수
def countNum(seq, k):
counts = {}
# sequence의 원소별 개수를 셈
for i in seq:
if i in counts:
counts[i] += 1
else:
counts[i] = 1
# k+1 개 이상의 원소 반환 (num: 0으로 초기화)
return {num: 0 for num,count in counts.items() if count > k}
overk = countNum(seq, k)
longest = 0
start = 0 # sequence의 시작 0으로 초기화
for end in range(n): # sequence의 마지막 0으로 초기화
if seq[end] in overk: # overk를 고려해야 하는 경우
overk[seq[end]] += 1 # overk 원소의 count를 1 증가시킴
while overk[seq[end]] > k: # 부분 수열의 원소의 개수가 K개를 넘었을 때
if seq[start] in overk: # start가 수열에 포함된 원소의 개수가 K보다 큰 원소일 경우
overk[seq[start]] -= 1 # overk 원소 count 감소시킴
start += 1 # start를 앞으로 이동시킴
longest = max(longest, end - start + 1)
print(longest)
해당 예제를 가지고 코드 리뷰를 진행하겠다.
먼저, 전체 수열에서 K+1개 이상 있는 원소에 대해서만 조건이 걸리기 때문에,
전체 모든 원소를 고려하기 보다는 K+1개 이상 있는 원소만 고려할 수 있도록 countNum 함수를 통해 dictionary 형태로 만들어주었다. 따라서 overk는 다음과 같은 형태이다. 딕셔너리 형태를 사용한 이유는 투포인터 알고리즘을 적용할 때 value 값을 활용해서 count 해줄 것이기 때문이다.
longest 는 가장 긴 최장 연속 부분 수열의 길이를 담게 된다. 그리고 start와 end는 각각 수열의 앞과 끝을 나타내는 인덱스이다.
for문을 통해 end를 0부터 마지막까지 반복하게 된다. iteration을 하나씩 살펴보면,
- start = 0, end = 0
- longest = 1
- start = 0, end = 1
- overk = {2 : 1, 6 : 0}
- longest = 2
- start = 0, end = 2
- overk = {2 : 2, 6 : 0} 가 되므로 while문으로 이동해서 start를 앞으로 한칸씩 이동시키면서 2를 찾음. 2를 만나면 overk = {2 : 1, 6 : 0}이 되고 start = 2
- longest = 2
- start = 2, end = 3 ~5
- longest = 2~4
- start = 2, end = 6
- overk = {2 : 1, 6: 1}
- longest = 5
- start = 2, end = 7
- overk = {2 : 1, 6 : 2} 가 되므로 while문으로 이동해서 start를 앞으로 한칸씩 이동시키면서 6을 찾음, 6을 만나면 overk = {2 : 0, 6 : 1} 이 되고(start가 6을 찍기 전에 2를 먼저 찍음 따라서 윈도우에 2가 존재하지 않음!), start = 7 이된다.
- longest = 5
- 나머지 돌아도 longest 업데이트 되지 않음@!
'코딩테스트 > 백준(Python)' 카테고리의 다른 글
[백준][Python] 13549번. 숨바꼭질3 (0) | 2024.07.10 |
---|---|
[백준][Python] 3758번. KCPC(실버2) (0) | 2024.07.07 |
[백준][Python] 15989번 1, 2, 3 더하기 4(골드5) (0) | 2024.07.06 |
[그리디][파이썬][백준] 13305번 주유소 (0) | 2023.03.30 |
[그리디][파이썬][백준] 1541번 잃어버린 괄호 (0) | 2023.03.30 |