20922. [Python]겹치는 건 싫어

1. 문제

 

https://www.acmicpc.net/problem/20922

 

 

2. 접근 방법

 

• 시간 제한: 1초
• 메모리 제한: 1024MB
• 투 포인터

 

3. 파이썬 코드

 

N, K = map(int, input().split())
num_list = list(map(int, input().split()))
num_cnt = [0] * 100001
# 시작
left = 0
# 끝
right = 0
# 최대 길이 체크
max_length = 0
# N까지 반복문 진행
while right < N:
    # num_list 의 값 나올 때마다 1씩 증가
    num_cnt[num_list[right]] += 1
    # K 개보다 더 많이 나오는 경우
    if num_cnt[num_list[right]] > K:
        # max_length 값 갱신
        if max_length < right - left:
            max_length = right - left
        # num_cnt에서 num_list의 값이 K 보다 작을때까지 left 값증가하며 반복
        while num_cnt[num_list[right]] > K:
            num_cnt[num_list[left]] -= 1
            left += 1
    right += 1
# 맨 마지막 리스트 순회에서 값 갱신
else:
    if max_length < right - left:
        max_length = right - left
print(max_length)

 

4. 문제를 풀고난 후 생각

 

• 연속 부분 수열이 무엇인지 헷갈려서 조금 찾아본 후 무슨 의미인지 깨닫는데 시간이 소요됨.
• 기본적인 투 포인터 문제로 left 값을 언제 증가시킬지 생각을 해보면 쉽게 풀 수 있다.
• K 개의 중복된 수를 허용하기 때문에 index 를 통해서 몇의 숫자가 몇번 나왔는지 체크하는 식으로 문제에 접근했으며 K 개를 넘는 숫자가 나온 경우 K 개 보다 적어질때까지 left 값을 증가시키며 숫자들을 빼는 식으로 문제를 풀었다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• 투 포인터