[백준 20922] 겹치는 건 싫어 - JAVA

문제

홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다.
특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다.
도현이를 위해 같은 원소가 $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$)

---

출력

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

---

접근 방법

처음 지문을 봤을 때 최장 연속 부분 수열의 길이라는 지문을 읽고
이게 뭐지? LIS인가?
최장 연속 부분 수열이 뭐지?
하면서 문제를 읽어도 잘 이해가 되지 않았습니다.

어렵게 생각하지 않고 단순하게 부분 수열이라는 것을 읽고
전체 수열에서 연속되는 부분 수열이 최대가 되도록 하는 것을 구하면 되지 않을까?
라고 생각하고 입력과 출력을 확인하니 이해가 됐습니다.

이해한 후에는 투 포인터를 사용하면 될 것 같다는 생각이 들었습니다.
단순 투 포인터 문제이기 때문에 투 포인터 알고리즘을 학습했다면 방법을 간단하게 떠올리실 수 있습니다.

• 부분 수열에서 특정 숫자의 수가 K개 미만이어야 하기 때문에 개수를 저장하도록 계수 정렬 방식의 배열을 선언하면 간단하지 않을까? 라고 생각했고 숫자는 10만보다 작거나 같은 양의 정수이므로 가능하다고 판단해서 사용했습니다.
• start와 end 인덱스를 0으로 두고 end를 증가시키는 투 포인터 알고리즘을 수행
  • while문에 들어가면 현재 인덱스 위치(end)의 숫자를 확인합니다.
  • 만약 해당 숫자의 수가 K 초과라면
    start 인덱스의 숫자의 수를 감소(counting[arr[start]])시키고 start 인덱스를 증가시킵니다.
  • 만약 해당 숫자의 수가 K 이하라면
    end 인덱스에 위치한 숫자의 개수를 증가시키고 end 인덱스를 증가시키고 최댓값 갱신 로직을 수행합니다.
• 이 작업을 end 인덱스가 N이 될 때까지 반복하면 최장 연속 부분 수열을 구할 수 있습니다.

---

코드

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


class Main {
    static StringTokenizer st;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int[] arr = new int[N];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int start = 0;
        int end = 0;
        int max = 1;

        int[] counting = new int[100001];

        while (end < N) {
            int num = arr[end];
            if (counting[num] == K) {
                counting[arr[start]]--;
                start++;
            }

            else {
                counting[num]++;
                end++;
                max = Math.max(max, end - start);
            }
        }

        System.out.println(max);
    }
}

이 문제에서 while의 조건에서 왜 start < N은 제외했냐하면
start 인덱스가 증가하는 조건을 확인해보면 알 수 있는데

특정 숫자의 개수가 K개 이상일 때만 start 인덱스가 증가하기 때문에
end 인덱스보다 클 수가 없는 상황이기 떄문에 제외했습니다!