https://www.acmicpc.net/problem/20922
문제
홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 K개 이하로 들어 있는 최장 연속 부분 수열의 길이를 구하려고 한다.
100,000 이하의 양의 정수로 이루어진 길이가 N인 수열이 주어진다. 이 수열에서 같은 정수를 K개 이하로 포함한 최장 연속 부분 수열의 길이를 구하는 프로그램을 작성해보자.
입력
첫째 줄에 정수 N (1≤N≤200000)과 K (1≤K≤100)가 주어진다.
둘째 줄에는 a1,a2,...an이 주어진다 (1≤ai≤100,000)
출력
조건을 만족하는 최장 연속 부분 수열의 길이를 출력한다.
예제 입력 1
9 2
3 2 5 5 6 4 4 5 7
예제 출력 1
7
예제 입력 2
10 1
1 2 3 4 5 6 6 7 8 9
예제 출력 2
6+) 예제 입력 3
5 2
2 2 2 4 5+) 예제 출력 3
4풀이
package two_pointer;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main_20922 {
private static int lengthOfSequence;
private static int numberOfDuplicate;
private static int[] sequence;
private static int[] used = new int[100_001];
private static int maxLength;
public static void main(String[] args) throws IOException {
input();
process();
output();
}
private static void input() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
lengthOfSequence = Integer.parseInt(st.nextToken());
numberOfDuplicate = Integer.parseInt(st.nextToken());
sequence = new int[lengthOfSequence];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < lengthOfSequence; i++) {
sequence[i] = Integer.parseInt(st.nextToken());
}
}
private static void process() {
int left = 0;
int right = 0;
while (left < lengthOfSequence && right < lengthOfSequence) {
while (right < lengthOfSequence && used[sequence[right]] < numberOfDuplicate) {
used[sequence[right]]++;
right++;
}
int length = right - left;
if (length > maxLength) {
maxLength = length;
}
used[sequence[left]]--;
left++;
}
}
private static void output() {
System.out.println(maxLength);
}
}