8045 : 중복 없는 서브배열
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
크기가 $N$인 정수 배열과 정수 $K$가 주어집니다.
서로 다른 원소의 개수가 최대 $K$개 이하인 연속된 부분 배열(서브배열)의 총 개수를 구하는 프로그램을 작성하시오.
[제약 조건]
• $1 \le N \le 200{,}000$
• $1 \le K \le N$
• $1 \le x_i \le 10^9$
서로 다른 원소의 개수가 최대 $K$개 이하인 연속된 부분 배열(서브배열)의 총 개수를 구하는 프로그램을 작성하시오.
[제약 조건]
• $1 \le N \le 200{,}000$
• $1 \le K \le N$
• $1 \le x_i \le 10^9$
입력 설명
첫째 줄에 배열의 크기 $N$과 기준 개수 $K$가 공백으로 구분되어 주어집니다. ($1 \le N \le 200,000$, $1 \le K \le N$)
둘째 줄에 $N$개의 정수 $x_1, x_2, \ldots, x_N$이 공백으로 구분되어 주어집니다. ($1 \le x_i \le 10^9$)
둘째 줄에 $N$개의 정수 $x_1, x_2, \ldots, x_N$이 공백으로 구분되어 주어집니다. ($1 \le x_i \le 10^9$)
출력 설명
서로 다른 원소의 개수가 최대 이하인 서브배열의 총 개수를 출력합니다. (출력값이 64비트 정수 범위를 가질 수 있음에 유의하십시오.)
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 2
1 2 3 1 1
출력 예시
COPY
복사되었습니다!
복사되었습니다!
10도움
이 문제는 투 포인터(Two Pointers) 또는 슬라이딩 윈도우(Sliding Window) 기법을 사용해 $O(N)$ 시간 복잡도 안에 풀 수 있습니다.
오른쪽 포인터
오른쪽 포인터
r을 한 칸씩 증가시키며 빈도수 딕셔너리에 원소를 기록합니다. 딕셔너리에 존재하는 고유 원소의 수가 $K$를 초과하는 순간, 왼쪽 포인터 l을 당기며 해당 원소의 빈도를 줄여나갑니다. 고유 원소 수가 $K$ 이하가 되었을 때, r을 끝으로 하는 조건을 만족하는 서브배열의 개수는 r - l + 1개가 되므로 이를 누적합해 나갑니다.