[ 20922 ] [ queue ] 겹치는 건 싫어

문제 설명

---

문제

홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 K개 이하로 들어 있는 최장 연속 부분 수열의 길이를 구하려고 한다.

 100000 이하의 양의 정수로 이루어진 길이가 N인 수열이 주어진다. 이 수열에서 같은 정수를 K개 이하로 포함한 최장 연속 부분 수열의 길이를 구하는 프로그램을 작성해보자.

입력

첫째 줄에 정수 N (1≤N≤200000)과 K(1≤K≤100)가 주어진다.

둘째 줄에는a1,a2,...an{a_1, a_2, ... a_n}$이 주어진다 (1≤ai≤100000)

출력

조건을 만족하는 최장 연속 부분 수열의 길이를 출력한다.

---

풀이 과정

• 원래는 투 포인터 문제 분류여서 투포인터 방식으로 구현하려 했으나.. 큐로 구현하는게 훨씬 편할 것 같아서 큐로 구현, 구현해보니 투포인터랑 크게 다를건 없는거 같다.

1. 원소의 개수를 매번 큐에서 세는 경우, 시간 초과가 발생할 수도 있으니 딕셔너리로 원수의 개수를 추가하면서 세줌.
2. 원소를 순차적으로 접근하면서 추가하였을 때, 원소의 개수가 K개를 넘는 경우
   • 추가한 원소를 빼줄때까지 큐의 왼쪽에서부터 빼준다.
3. 매 순간 queue가 언제 최대 길이가 되는지 저장해둔 다음, 마지막에 출력해주면 된다. (최장 연속 부분 수열의 길이)

---

소스 코드

import sys
from collections import deque
input = sys.stdin.readline
N, K = map(int, input().rstrip().split())
numbers = list(map(int, input().rstrip().split()))
sequence = set()
dup_count = {i:0 for i in range(1, 100001)}
answer = 0

queue = deque()
for number in numbers:
    queue.append(number)
    dup_count[number] += 1
    # number에서 중복 문제 걸림
    if dup_count[number] > K:
        # number가 나올때까지 queue에서 싹 빼주어야 함.
        while queue:
            temp = queue.popleft()
            dup_count[temp] -= 1
            if temp == number:
                break
    answer = max(answer, len(queue))

print(answer)