[Python/코테] 백준 20922 겹치는 건 싫어

20922 겹치는 건 싫어

문제 및 조건 설명: https://www.acmicpc.net/problem/20922

알고리즘 설계

💡idea.

시작 인덱스와 끝 인덱스, 두개의 포인터로 배열을 순회하여 문제를 해결할 수 있다. 

배열을 전부 검사하기 전까지 미리 중단할 수 없다. 

 

🎲step.

1. 한 칸씩 검사하며 새로운 칸의 등장 횟수를 센다.

2. 등장 횟수가 k번을 초과하는 순간 시작 또는 끝 인덱스를 이동(증가)해준다.

3. 인덱스 변경 시 마다(=한 칸 이동마다) 최대 길이값을 저장해둔다.

4. 끝 인덱스가 배열의 끝에 도달하면 종료한다.

 

알고리즘 구현

코드 출처: https://kimmeh1.tistory.com/474

import sys

n, k = map(int, input().split())
arr = list(map(int, sys.stdin.readline().split()))

start = 0
end = 0

count_arr = [0] * (max(arr)+1)
answer = 0

while end < n:
    # start = end = 0 에서 시작해서, 하나씩 센다.
    # end가 앞으로 가며 해당 원소의 카운팅이 증가하고
    if count_arr[arr[end]] < k:
        count_arr[arr[end]] += 1
        end += 1
    else:
        # start가 앞으로 갈 때 원소의 카운팅이 감소한다.
        count_arr[arr[start]] -= 1
        start += 1
    answer = max(answer, end - start)

print(answer)

나다어

• 배열의 순회가 필요할 때, 한 칸씩 검사하는 것이 제일 효율적일 수도 있다.