[Java] 백준 20922번: 겹치는 건 싫어

[문제 바로 가기] - 겹치는 건 싫어

💡 일단 생각하기!

투 포인터 연습하기 좋은 문제! 아직 투 포인터에 익숙하지 않아 풀기 좋은 문제였다.

start와 end를 모두 0으로 잡고 시작한다.
end는 N을 넘으면 안되고 end 인덱스의 값이 중복 개수(=K)를 넘지 않을 때까지 end++를 해준다.
만약 K를 넘는다면 start 인덱스의 값에서 하나 빼주고 start++를 하며 이 과정을 반복해준다.
수열의 길이는 start++를 할 때마다 갱신해주며 최대값을 저장한다.

풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/**
 * 백준 20922번 겹치는 건 싫어
 * - 투 포인터 사용
 * 
 * 메모리 : 37104kb 시간 : 244ms
 */
public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken()); // 수열 길이
		int K = Integer.parseInt(st.nextToken()); // 같은 정수 제한 개수
		
		int arr[] = new int[N]; // 수열 넣는 배열
		int num[] = new int[100001]; // 정수 개수 세는 배열
		
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		int max = 0; // 최장 수열 길이
		int start = 0;
		int end = 0;
		
		// 투 포인터
		while (end < N) {
			// 중복 개수를 넘지 않을 때까지 end++
			while (end < N && num[arr[end]] < K) {
				num[arr[end]]++;
				end++;
			}
			
			// 중복 개수 넘을 경우 start 인덱스 하나 빼주고 start++ 
			max = Math.max(max, end - start);
			num[arr[start]]--;
			start++;
		}
		
		System.out.println(max);
	}
}