맛집 순례
실버 III의견: 0
미식가 유진은 \(N\)개의 식당이 일렬로 늘어선 거리에서 맛집 순례를 계획하고 있다. 각 식당은 \(1\)부터 \(N\) 사이의 요리 종류 번호를 하나씩 가지고 있다.
유진은 연속된 식당들을 방문하되, 방문한 식당의 요리 종류가 최대 \(K\)가지를 넘지 않도록 하고 싶다. 이 조건 아래 방문할 수 있는 가장 많은 식당의 수를 구하여라.
- \(1 \le K \le N \le 200\,000\)
- 각 식당의 요리 종류 번호는 \(1\) 이상 \(N\) 이하의 정수이다.
첫째 줄에 식당의 수 \(N\)과 요리 종류 제한 \(K\)가 공백으로 구분되어 주어진다.
둘째 줄에 각 식당의 요리 종류 번호 \(N\)개가 공백으로 구분되어 주어진다.
조건을 만족하는 연속 구간의 최대 길이를 출력한다.
7 2
1 2 1 3 2 1 4
3
서로 다른 값이 최대 \(2\)개인 가장 긴 연속 구간을 찾는다. \([1,2,1]\), \([2,1,3]\) 등도 크기 \(3\)이지만, \([1,3,2,1]\)은 서로 다른 값 \(3\)개라 안 된다. 최대는 \([1,2,1]\) 또는 \([3,2,1]\) 등 길이 \(3\)이다. 사실 \([1,2,1]\) 길이 \(3\)이 최대이다.
5 1
3 3 3 3 3
5
모든 원소가 \(3\)으로 서로 다른 값이 \(1\)개뿐이므로 전체 배열 길이 \(5\)가 답이다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
맛집 순례
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
맛집 순례