Double Rainbow

면접 대비

시간 제한1초메모리 제한1024 MB

요약

색 배열과 k개의 색이 주어질 때, 모든 색을 포함하면서 여집합도 모든 색을 포함하는 가장 짧은 연속 구간의 길이를 구하고, 없으면 0을 출력한다.

난이도: 보통10점 중 6점
유형: 투 포인터, 슬라이딩 윈도우, 누적 합, 배열
정답자: 아직 제출이 없습니다

문제

$x$ 축 위에 $n$ 개의 점으로 이루어진 집합 $P$ 가 있고, 각 점은 $1, 2, \dots, k$ 중 하나의 색으로 칠해져 있다. $k$ 개의 색 각각에 대해, $P$ 안에 그 색으로 칠해진 점이 적어도 하나 있다. $P$ 에서 연속한 점들로 이루어진 집합 $P'$ 에 대해, $P'$ 과 $P \backslash P'$ 이 모두 각 색의 점을 적어도 하나씩 포함하면 $P'$ 이 double rainbow를 만든다고 한다. 아래 그림을 예로 보자. 집합 $P$ 는 열 개의 점으로 이루어져 있고, 각 점은 $1$ , $2$ , $3$ , $4$ 중 하나의 색으로 칠해져 있다. 사각형 안에 있는 연속한 다섯 점의 집합 $P'$ 이 double rainbow를 만든다.

점 집합 $P$ 와 색의 개수 $k$ 가 입력으로 주어지면, double rainbow를 만드는 $P'$ 의 최소 크기를 계산해 출력하는 프로그램을 작성하라.

입력

프로그램은 표준 입력에서 데이터를 읽는다. 입력의 첫 줄에는 두 정수 $n$ 과 $k$ ( $1 ≤ k ≤ n ≤ 10,000$ )가 주어지며, $n$ 은 $P$ 에 있는 점의 개수, $k$ 는 색의 개수이다. 다음 $n$ 개의 줄에는 각각 $1$ 이상 $k$ 이하의 정수가 하나씩 주어지며, $i$ 번째 줄은 $P$ 에서 왼쪽에서 $i$ 번째 점의 색을 나타낸다.

출력

프로그램은 표준 출력에 결과를 쓴다. 정확히 한 줄을 출력하라. 그 줄에는 double rainbow를 만드는 $P'$ 의 최소 크기를 출력한다. 그러한 $P'$ 이 없으면 0을 출력한다.

예제2

예제 1
입력
```
10 4
1
2
3
1
1
4
2
4
3
3
```
예상 출력
```
5
```
예제 2
입력
```
6 3
1
1
2
2
3
3
```
예상 출력
```
0
```