[백준/python] 20922번 겹치는 건 싫어

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

20922번: 겹치는 건 싫어

 

🖇 투포인터

 

문제설명

길이가 n인 수열이 입력으로 주어지고, 그 수열에서 중복되는 숫자가 k개 이하인 "가장 긴 연속 부분 수열"의 길이를 출력하는 문제다.

코드

from collections import defaultdict
input=__import__('sys').stdin.readline
n,k=map(int,input().split())
li=list(map(int,input().split()))
left, right = 0, 0
dd = defaultdict(int)
ans = 0
while True:
    if right == n:
        break
    if dd[li[right]] < k:
        dd[li[right]] += 1
        right += 1
    else:
        dd[li[left]] -= 1
        left += 1
    ans = max(right-left, ans)
print(ans)

 

문제풀이

처음에는 테스트 케이스가 잘 이해되지 않았다. 첫번 째 테스트 케이스로 예를 들어 설명해보자면, 

9 2
3 2 5 5 6 4 4 5 7

"3 2 5 5 6 4" 가 k=2 이하를 만족하는 최장 수열이라고 생각했다. 중복되는 5가 2개이므로 여기서 그쳐야한다는 이유에서.

그 다음 4까지 들어오면 5가 2개, 4가 2개이므로 총 4개의 수가 중복된다고 판단했다.

하지만 이 문제에서는, 중복되는 숫자 개수의 최대가 k를 넘지 않으면 된다.

"3 2 5 5 6 4 4" 의 경우에는 5가 2개, 4가 2개이므로 중복되는 개수의 최대가 2이다. k=2를 만족하는 것이다.

반면에,

"3 2 5 5 6 4 4 5" 의 경우에는 4가 2개지만 5가 3개이므로 중복되는 수의 최대 개수는 3이다. 그러므로 성립하지 않는다.

n이 최대 200,000이므로 가능한 모든 부분 수열을 모두 체크하는 것은 불가능하므로, 투 포인터를 사용해서 최대 길이를 구할 수 있다.

defaultdict을 사용하여, 원소의 개수를 저장해주면서(defaultdict[li[right]] += 1) 오른쪽으로 나아간다. (right += 1)

그러다가 defaultdict의 value값이 k와 같아지면 right 포인터의 이동을 멈추고 value값이 다시 k보다 작아질 때까지 left 포인터를 이동시킨다.

각각의 실행마다 right-left (부분수열의 길이)를 체크해서, 가장 큰 부분 수열을 출력하면 된다.

 

메모

defaultdict을 알게 된 이후에는 아마 처음 써본 것 같은데, 꽤 유용한 것 같다.

물론 일반적인 dict을 선언해서, key값이 저장되어 있을 땐 += 1 을 해주고, 없을 때는 dict[key] = 1 과 같은 방식으로 새로 넣어주어도 되긴 하지만, 조건문이 더 많이 필요하고 복잡해질 것이다. (그렇게 하다가 헷갈려서 그냥 defaultdict을 사용했다.)

또한 right을 1부터 시작하려고 했는데, 그랬다면 n==1일 때와 같은 경우에는 예외 처리를 해줘야 하기 때문에 시작은 동일하게 하는 걸로!