/
/

[백준] 20922 겹치는 건 싫어

투포인터
avatar
chae
2024.12.30
·
4 min read
2696

🔗 문제 링크

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

💻 코드

import sys
input = sys.stdin.readline 
from collections import defaultdict

n,k = map(int,input().split())
nums = list(map(int,input().split()))
dic = defaultdict(int) # 각 숫자의 등장 횟수

left,right = 0,0 # 투 포인터
cur_cnt = 0 # 현재 슬라이딩 윈도우 내의 유효한 연속 숫자 개수
result = 0 # 가장 긴 부분 수열의 길이 

while right < n:

    dic[nums[right]] += 1

    while dic[nums[right]] > k:
        dic[nums[left]] -= 1
        left += 1
        result = max(result,cur_cnt)
        cur_cnt -= 1

    if dic[nums[right]] <= k:
        cur_cnt += 1

    
    right += 1

result = max(result,cur_cnt)
print(result)

🤷‍♂️ 풀이

접근 방법

  • 투 포인터를 이용해서 풀었다.

  • 리스트 양 끝을 left, right 포인터를 조작해 조건을 만족하는 가장 긴 구간을 탐색

  • 각 숫자의 등장 횟수를 관리하기 위해 편리하게 defaultdict을 사용했다.

코드 분석

  • right 포인터를 배열의 길이 범위 내에서 확장하며 숫자의 빈도를 업데이트

  • dic[nums[right]] > k 라면 범위를 초과한 것이기에 left를 이동시켜 윈도우를 조정

    • 이 때 nums[left] 즉, 가장 왼쪽에서 없어진 숫자 개수를 딕셔너리에서 빈도 감소

    • 이 후 윈도우의 시작점 left를 오른쪽 한 칸으로 이동

    • 이동시켰으므로, 윈도우 내의 유효한 길이를 계산해 현재 최대값을 result에 업데이트

      • 왜 업데이트 해야하냐면, 윈도우의 길이가 줄어드는 경우를 대비해 갱신하는 것

    • 왼쪽 포인터가 이동하면서 윈도우 내 유효한 숫자의 개수를 감소

  • 조건을 만족하는 경우에는 유효한 숫자 개수 증가

  • right 포인터 한 칸 이동해 다음 숫자 처리

  • 루프가 끝난 후에도 마지막 구간의 길이가 최댓값인지 확인해야한다.

문제의 본질

🔍 왜 while dic[nums[right]] > k: 에서 if가 아니라 while을 사용할까?

-> 슬라이딩 윈도우의 조건을 계속 만족시키기 위해 left를 여러 번 이동시킬 수 있기 때문이다.

-> nums[right]의 등장 횟수가 k를 초과한다면, 윈도우를 계속 축소해줘야한다.

결국 슬라이딩 윈도우가 항상 유효한 상태를 유지할 수 있게 해주는 것이 문제의 본질이다.

  • 내가 고려하지 못한 예제

    • n = 10, k = 1

    • nums = [5,2,3,4,5,5,7,8,9,10]

시간복잡도

  • right는 배열을 끝까지 탐색

  • left는 필요할 때만 증가하며, 최대 n-1번까지 이동 가능

  • 딕셔너리는 nums 배열의 각 원소에 대한 빈도 저장

  • while right < n O(n)

  • while dic[nums[right]] > k O(n)

  • 딕셔너리의 연산은 모두 O(1)

  • 외부 루프와 내부 루프가 중첩되지 않고 독립적으로 작동 -> O(n) + O(n) = O(n)

    • 모든 조합을 반복하지 않기 때문이다.

- 컬렉션 아티클