[백준 20922] 겹치는 건 싫어

🍎[백준 20922] 겹치는 건 싫어

문제링크

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

20922번: 겹치는 건 싫어

 

⚾ 코드

n, k = map(int, input().split())
number = list(map(int, input().split()))

need = {} 

for i in set(number):
    # 사용 가능한 수 만큼 저장
    # 예) need = {1:2, 2:2, 3:3, 4:2}
    need[i] = k

left, right = 0, 0
result = 0

while right < n:
    num = number[right] # 현재 탐색하고 있는 숫자

    if need[num] > 0: # 아직 사용할 수 있다면
        need[num] -= 1 # need에서 감소시키고
        right += 1 # right 포인터 증가
    else: # 만약에 다 사용했다면
        if result < right-left: # 결과 갱신
            result = right-left

        while need[number[right]] < 1: # right에 있던 숫자가 범위에서 빠질 때 까지
            need[number[left]] += 1 # 왼쪽 포인터 증가
            left += 1

if result < right-left:
    result = right-left
    
print(result)

 

🔔 해결 과정 & 깨달은 점

- 투 포인터 방법을 이용해서 풀었다.

- need에는 각 숫자가 k만큼 담겨있다.

- right를 증가시키면서 탐색을 시작한다. right에 해당하는 숫자를 need에서 감소시킨다.

- need[num] 이 0 이 되었다는 것은 포함할 수 있는 횟수만큼 다 포함했다는 뜻이므로, 더이상 right를 증가시켜서는 안 된다.

- 결과를 저장한다.

- 현재 포인터에 있는 right를 더이상 담지 못해 종료 된 것이므로, 왼쪽 포인트를 하나씩 증가시키며 숫자를 뺀다.

- 중복된 숫자가 빠질 때 까지 반복한다. (while need[number[right]] < 1:)

- 중복된 숫자가 빠지면, 다시 위의 과정을 반복한다.

- 최종적으로 right-left가 가장 긴 것이 정답이 될 것이다.

 

- 처음에는 중복 된 숫자가 나오면, left를 right로 바꿔서 탐색을 시작했다. 그렇게 하니 모든 경우를 탐색할 수 없는 문제가 발생하여 위와 같이 방법을 수정하여 다시 코드를 구현했다.