[BOJ_20922] 겹치는 건 싫어

설명

---

투 포인터로 접근하였고 처음 숫자의 크기만큼 배열을 짜서 각 숫자마다 가진 갯수를 뒤지는 식으로 풀었다. 사실 구현 할 때 맵 형태로 구현 해보았으나 생각보다 맵을 써서 푸는 것 보다 배열이 메모리나 속도 측면에서 더 빨랐다.

 

코드

---

package two_pointer;

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

public class BOJ_20922 {
    public static void main(String[] args) throws Exception{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tk = new StringTokenizer(in.readLine()," ");

        int N = Integer.parseInt(tk.nextToken());
        int K = Integer.parseInt(tk.nextToken());
        int arr[] = new int[N];
        int count[] = new int[100001];
        tk = new StringTokenizer(in.readLine()," ");
        for(int i = 0; i < N; i++){
            arr[i] = Integer.parseInt(tk.nextToken());
        }
        int start = 0;
        int end = 0;
        int ans = 0;
        while(start < N){
            while(end < N && count[arr[end]] < K){
                count[arr[end]]++;
                end++;
            }
            ans = Math.max(end - start,ans);
            count[arr[start]]--;
            start++;
        }
        System.out.println(ans);
    }
}

20922번: 겹치는 건 싫어