5회 문제풀이 02 / ABC 210 C - Colorful Candies

ABC 210 C - Colorful Candies

【문제 개요】

N개의 사탕이 일렬로 놓여 있습니다. 각 사탕에는 색상을 나타내는 정수가 할당되어 있습니다.
i = 1, 2, …, N에 대해서 왼쪽에서 i번째의 사탕의 색은 색cᵢ입니다.
타카하시군은 늘어서있는 사탕중에 연속해서 늘어선 K개의 사탕을 가져가는것이 가능합니다.
즉, 1 ≤ i ≤ N - K + 1를 만족하는 정수 i를 선택하고 왼쪽에서 i번째, i + 1번째, i + 2번째, …, i + K - 1번째의 사탕을 받아갈 수 있습니다.
타카하시군은 각각의 색의 사탕을 먹고싶기때문에 받는 사탕에 포함되어있는 색의 종류수가 많을수록 기뻐합니다.
타카하시군이 가져가는 사탕에 포함된 색의 종류수의 최대치를 출력하시오.

힌트 : 슬라이딩 윈도우 기법

【전제】

• 입력은 모두 정수이다.
• 1 ≤ K ≤ N ≤ 3 x 10⁵
• 1 ≤ cᵢ ≤ 10⁹

【입력 형태】

N K
c₁ c₂ ... cₙ

【출력 형태】

타카하시군이 가져가는 사탕에 포함된 색의 최대수를 출력하라.

【예시】

입력 예 1

7 3
1 2 1 2 3 3 1

출력 예 1

3

타카하시군이 왼쪽에서 3번째부터 5번째까지의 사탕을 받아가면 1, 2, 3의 3종류가 되므로 이것이 최대입니다.

입력 예 2

5 5
4 4 4 4 4

출력 예 2

1

타카하시군은 모든 사탕을 가져갈 수 있지만 어떤 사탕을 가져가도 4의 색만 가져가기때문에 색의 종류의 최대값은 1종류입니다.

입력 예 3

10 6
304621362 506696497 304621362 506696497 834022578 304621362 414720753 304621362 304621362 414720753

출력 예 3

4

출처 : https://atcoder.jp/contests/abc210/tasks/abc210_c