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

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

 

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

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

---

1.  아이디어

 

카운팅 배열과 투 포인터 알고리즘을 활용하면 해결할 수 있다.

---

2. 문제풀이

 

수열의 앞쪽에 left, right 포인터를 설정한 후 right 포인터에 위치한 수가 카운팅 배열에서 K개 미만이면 포함할 수 있고, K개면 포함할 수 없다. 포함할 수 있으면 포함하고 right 포인터를 오른쪽으로 이동, 포함할 수 없으면 left 포인터의 수를 카운팅 배열에서 빼주고 left 포인터를 오른쪽으로 이동하는 과정을 반복하면 됐다.

---

3. 코드

 

import java.io.*;
import java.util.*;

public class Main {

    private static final int MAX = 100_000;

    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[] arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int left = 0;
        int right = 0;
        int len = 0;
        int[] cntArr = new int[1 + MAX];

        while (right < N) {
            int cnt = cntArr[arr[right]];

            if (cnt < K) {
                cntArr[arr[right]]++;
                right++;
                len = Math.max(len, right - left);
            } else {
                cntArr[arr[left]]--;
                left++;
            }
        }

        System.out.println(len);
    }
}

---

4. 후기