https://www.acmicpc.net/problem/20922
20922번: 겹치는 건 싫어
홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열
www.acmicpc.net
저는 해당 문제를 투포인터를 이용해 문제를 해결하였습니다.
투포인터를 통해 해당 사이의 숫자가 몇번나왔는지를 map으로 저장하여 만약 해당 숫자가 k이상이라면 시작 포인트를 줄여나가면서 k가 되도록 구현하였습니다.
package BOJ.twopoint;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;
import java.util.function.Function;
public class BOJ_20922 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine()," ");
Function<String,Integer> stoi = Integer::parseInt;
int n = stoi.apply(st.nextToken());
int k = stoi.apply(st.nextToken());
st = new StringTokenizer(br.readLine()," ");
int[] input = new int[n];
for(int i = 0 ; i < n ; i++){
input[i] = stoi.apply(st.nextToken());
}
Map<Integer,Integer> map = new HashMap<>();
int si = 0;
int ei = 0;
int result = 0;
while(true){
// System.out.println(si+" "+ei);
int num = input[ei];
while(map.getOrDefault(num,0) >= k){
int prev = input[si++];
map.merge(prev,0,(v1,v2)->v1-1);
}
result = Math.max(result,ei-si+1);
map.merge(num,1,(v1,v2)-> v1+1);
ei++;
if(ei >= n){
break;
}
}
System.out.println(result);
}
}