백준 20922: 겹치는 건 싫어 - 투 포인터

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

20922번: 겹치는 건 싫어

이 문제는 투포인터를 통해 풀 수 있습니다.

 

포인터 두 개 (p1, p2)를 선언한 하고, p2를 옮겨가며 현재 p2가 가리키는 숫자가 총 몇 번 나왔는지 count 해줍니다.

(dictionary 활용)

 

현재까지 나온 숫자 중 중복되는 것이 K가 넘을 때까지 p2를 옮겨주고, 넘게 되면 반복문에서 나와 한 칸 앞으로 p2를 되돌려줍니다.

(초과되기 바로 직전에 p2가 위치함)

 

최대 길이를 구해준 후, p1을 오른쪽으로 옮겨줍니다. 이 때 옮기기 전에 p1이 가리키는 값의 빈도수를 줄여줍니다.

 

from sys import stdin
input = stdin.readline

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

p1, p2 = (0, 0)
frequency = dict()
frequency[seq[p1]] = 1
max_length = 0


while p1 < n and p2 < n:
    index_error = False
    while frequency[seq[p2]] <= k:
        try:
            p2 += 1
            if seq[p2] not in frequency:
                frequency[seq[p2]] = 1
            else:
                frequency[seq[p2]] += 1
        except IndexError:
            index_error = True
            break
    if not index_error:
        frequency[seq[p2]] -= 1
    p2 -= 1

    max_length = max(max_length, p2 - p1 + 1)

    frequency[seq[p1]] -= 1
    p1 += 1

print(max_length)