[BOJ, python] 20922번_겹치는 건 싫어

이 글은 Velog에서 이전한 글입니다. Velog 원문 보기

백준 20922번

문제가 짧아서 좋다. 이런식으로 수열을 탐색을 요구하는 문제는 대부분 투포인터 알고리즘을 사용하라는 뜻이다.

투포인터 알고리즘?
이름 그대로 두 개의 포인터를 사용해 탐색을 하는 것이다.
대표적으로 시작 지점은 start와 끝 지점인 end를 두고, 문제 조건에 만족하는 경우 end를 옮기다가 문제 조건을 위반하는 순간 start의 위치를 문제 조건을 충족하는 위치까지 변경해주는 것이다.

나는 이 문제를 아래처럼 세부 문제로 나눴다.

1. *부분 수열의 원소의 갯수가 K를 넘지않도록 하려면 부분 수열 원소의 갯수를 따로 저장해야한다. *
   • 딕셔너리 활용, List도 가능하지만 딕셔너리가 효율적임
2. 원소 x의 갯수가 K개를 넘는 순간 start의 위치를 현재 부분 수열 중 x가 처음 등장하는 위치로 옮겨줘야한다.
   • 반복문을 사용해 start를 한 칸씩 이동하면서 현 위치의 숫자 갯수를 딕셔너리에서 감소시키고, x에 도달했다면 start의 위치는 x의 인덱스 +1

이 2가지 문제를 해결했다면 나머지는 코드로 구현하면 끝이다.

1차 풀이 코드

import sys
input = lambda: sys.stdin.readline().rstrip()
# 같은 원소가 K개 이하로 들어있는 최장 연속 부분 수열의 길이
N, K = map(int, input().split()) # 수열 길이, 정수 제한 갯수
arr = list(map(int, input().split()))

dict = {}
for i in arr:
    if i in dict:
        continue
    dict[i] = 0

start,end = 0,0

ans = 0
while end != N:
    x = arr[end]
    if dict[x] == K: # 이미 x의 갯수가 K와 같을시 x를 추가하면 문제가 됨.
        ans = max(ans, end-start)
        # start의 위치를 x가 처음나오는 위치까지 변경
        while True:
            if arr[start] == x:
                dict[x] -= 1
                start += 1
                break
            else:
                dict[arr[start]] -= 1
            start += 1

    elif dict[x] < K:
        dict[x] += 1
        end += 1

print(ans)

1차 시도 실패

42%에서 테스트가 실패했다. 보통 42%까지 왔다면 풀이과정 자체는 대부분 맞지만 중간에 오류가 있는 것이다.

보통 이런 경우 여러 반례를 활용하면 오류를 찾기가 쉬운데 나는 아래 반례를 통해 오류를 검출했다.

반례
input
29 3
1 2 3 4 5 6 7 8 9 1 1 11 1 14 15 16 23 43 24 53 24 25 99 29 36 45 64 69 45
output
28
반례 모음

문제는 ans = max(ans, end-start)에 있었다. 현재 코드를 보면 if dict[x] == K의 경우(원소의 갯수가 K개가 되는 경우)에만 부분 수열 최장 길이를 초기화해주고 있었다.
원소의 갯수가 K개가 되지 않고 끝나는 경우에는 길이가 최신화 되지 않고 있던 것이다.

최종 풀이 코드

import sys
input = lambda: sys.stdin.readline().rstrip()
# 같은 원소가 K개 이하로 들어있는 최장 연속 부분 수열의 길이
N, K = map(int, input().split()) # 수열 길이, 정수 제한 갯수
arr = list(map(int, input().split()))

dict = {}
for i in arr:
    if i in dict:
        continue
    dict[i] = 0

start,end = 0,0

ans = 0
while end != N:
    x = arr[end]
    if dict[x] == K: # 이미 x의 갯수가 K와 같을시 x를 추가하면 문제가 됨.
        ans = max(ans, end-start)
        # start의 위치를 x가 처음나오는 위치까지 변경
        while True:
            if arr[start] == x:
                dict[x] -= 1
                start += 1
                break
            else:
                dict[arr[start]] -= 1
            start += 1

    elif dict[x] < K:
        dict[x] += 1
        end += 1

ans = max(ans, end-start)

print(ans)

결과