백준 - 겹치는 건 싫어(20922)

문제 링크 ▶︎ 백준 겹치는 건 싫어 20922

문제 파악

1 ≤ n ≤ 200,000 이라는 조건으로 인해 이중포문을 돌릴 수 없다.
이 문제는 투 포인터를 사용해야 할 것 같다.

그리고 1 ≤ k ≤ 100 이라는 조건으로 중복된 수를 카운트 하는 것도 한번에 수행해야 할 것 같다.

접근 방법

아이디어는 배열에 존재하는 aᵢ의 범위가 1 ~ 100,000 이므로 배열 길이 100,001개 짜리 cnt 배열을 생성 후, 여기에 배열 요소의 갯수를 카운트한다.
index = 0 을 가르키는 first와 last라는 두개의 인덱스 포인터를 생성하고, first는 각 인덱스에 담긴 숫자를 cnt 배열에 카운트++ 해주는 역할이고, 만약에 도착한 인덱스의 숫자의 카운트가 k개에 도달하게 되면, first는 멈추고 last가 출발한다.

last는 인덱스에 담긴 숫자를 체크하고 숫자에 해당하는 cnt배열을 카운트-- 해주는 역할을 한다. 만약 해당 인덱스에 담긴 숫자의 카운트가 k와 같아서 멈춘 first의 숫자가 last로 인해서 k보다 작아진다면 다시 first는 출발한다.

이 과정에서 first와 last의 간격이 정답이 된다.
계속 first와 last의 간격을 answer 에 저장해두고, answer의 최댓값이 되는게 정답이 된다.

코드

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

public 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()); // 1 ~ 200,000
        int k = Integer.parseInt(st.nextToken()); // 1 ~ 100

        int[] numbers = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            numbers[i] = Integer.parseInt(st.nextToken());
        }
        int first = 0;
        int last = 0;
        int[] cnt = new int[100001];
        int answer = 0;
        while (first < n) {
            if (cnt[numbers[first]] < k) {
                cnt[numbers[first]]++;
                first++;
                answer = Math.max(answer, first - last);
            } else {
                cnt[numbers[last]]--;
                last++;
            }
        }
        System.out.println(answer);
    }
}

개선 사항

아이디어를 생각해내는 과정이 복잡했기 때문에 슬라이딩 윈도우 방식이 훨씬 간단할 것이라 생각된다.