[Java/투포인터] 코드트리. 1이 k개 이상 존재하는 부분 수열

🤔 Intuition

명료하게 counting array를 이용하는 two pointer 문제이다.

🔎 Algorithm & Complexity

* @algorithm two pointer
* @time O(N) : two pointer -> 449 ms
* @memory O(N) : 42 MB

👨🏻‍💻 Logic

탐색할 때, 정답 갱신 조건과 탐색 종료 조건을 설정해주는 게 그나마 있는 출제 의도로 느껴졌다. 사실 체감상 단순 투포인터 템플릿을 이용하는 문제였다.

public class CodeTree_1이k개이상존재하는부분수열 {
    private static int[] arr;
    private static int[] cntarr = new int[3];
    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());
        arr = new int[n];

        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int j = 0;
        int min = (int) 1e9;
        cntarr[arr[0]]++;
        for (int i = 0; i < n; i++) {
            while (j + 1 < n && cntarr[1] < k) {
                cntarr[arr[++j]]++;
            }
            if (cntarr[1] >= k) {
                min = Math.min(j - i + 1, min);
            }
            if (j == n - 1) {
                break;
            }
            cntarr[arr[i]]--;
        }
        System.out.println(min == (int) 1e9 ? -1 : min);
    }
}