[백준][Python] 20922번. 겹치는 건 싫어(실버1)

문제

홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 𝐾개 이하로 들어 있는 최장 연속 부분 수열의 길이를 구하려고 한다.

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을 하나씩 살펴보면,

1. start = 0, end = 0

• longest = 1

1. start = 0, end = 1

• overk = {2 : 1, 6 : 0}
• longest = 2

1. start = 0, end = 2

• overk = {2 : 2, 6 : 0} 가 되므로 while문으로 이동해서 start를 앞으로 한칸씩 이동시키면서 2를 찾음. 2를 만나면 overk = {2 : 1, 6 : 0}이 되고 start = 2
• longest = 2

1. start = 2, end = 3 ~5

• longest = 2~4

1. start = 2, end = 6

• overk = {2 : 1, 6: 1}
• longest = 5

1. 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

1. 나머지 돌아도 longest 업데이트 되지 않음@!