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

https://www.acmicpc.net/problem/20922

난이도

실버1

문제

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

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

입력

첫째 줄에 정수 $N$ ($1 \le N \le 200\,000$)과 $K$ ($1 \le K \le 100$)가 주어진다.
둘째 줄에는 ${a_1, a_2, ... a_n}$이 주어진다 ($1 \le a_i \le 100\,000$)

출력

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

내 코드

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

class Main {
	public static void main(String[] args) throws IOException {
		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[] nums = new int[N];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			nums[i] = Integer.parseInt(st.nextToken());
		}

		int start = 0;
		int max = 0;
		HashMap<Integer, Integer> map = new HashMap<>();
		for (int i = 0; i < N; i++) {
			map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
			while (map.get(nums[i]) > K) {
				map.put(nums[start], map.get(nums[start]) - 1);
				start++;
			}
			max = Math.max(max, i - start + 1);
		}
		System.out.println(max);
	}
}

슬라이딩 윈도우를 사용하여서 하나를 넣으면서 넣을때 마다 새로 넣은 값이 K보다 큰지 확인을 해준다.

만약 K보다 크다면 while문을 통해서 현재 이어진 부분의 가장 앞부터 하나씩 제외하면서 현재 추가한 값의 갯수가 K보다 작아질 때까지 갯수를 빼주고, start의 값은 1자리씩 올라온다.

그 과정이 마치면 최댓값을 한번 갱신해준다.