아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

겹치는 건 싫어

면접 대비

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

요약
수열과 한계 K가 주어질 때, 어떤 값도 K번을 넘지 않는 가장 긴 연속 부분 수열의 길이를 구한다.
난이도

보통10점 중 5점

유형
슬라이딩 윈도우, 투 포인터, 해시맵, 배열
정답자
아직 제출이 없습니다

문제

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

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

입력

첫째 줄에 정수 NN (1≤N≤200 0001 \le N \le 200\,000)과 KK (1≤K≤1001 \le K \le 100)가 주어진다.

둘째 줄에는 a1,a2,...an{a_1, a_2, ... a_n}이 주어진다 (1≤ai≤100 0001 \le a_i \le 100\,000)

출력

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

힌트

연속 부분 수열이란 그 수열의 원소를 하나 이상 연속하여 선택한 부분 수열을 말한다.

a=3,9,7,6,5a = {3, 9, 7, 6, 5} 일 때 9,7,69, 7, 6는 연속 부분 수열이고 3,6,53, 6, 5는 그렇지 않다.

예제2

  1. 예제 1

    입력
    9 2
    3 2 5 5 6 4 4 5 7
    
    예상 출력
    7
    
  2. 예제 2

    입력
    10 1
    1 2 3 4 5 6 6 7 8 9
    
    예상 출력
    6