[Baekjoon/JAVA] 20922 겹치는 건 싫어

 

처음에 dp로 풀어야 하나 싶다가 감이 너무 안와서 유형을 컨닝하고..(?) 풀었다.

투포인터로 풀면 쉽게 풀리는 거였는데 괜히 어렵게 생각하고 있었다...!

 

import java.io.*;
import java.util.*;
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());
        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 result = 1;

        int[] cnt = new int[Arrays.stream(arr).max().getAsInt() + 1];

        while (right < N) {
            // 수열의 조건을 만족하는 경우 right 증가
            if (cnt[arr[right]] < K) {
                cnt[arr[right]] += 1;
                right++;
            // 조건을 만족하지 못 하는 경우 left 증가
            } else {
                cnt[arr[left]] -= 1;
                left++;
            }
            result = Math.max(result, right - left);            
        }
        System.out.println(result);
    }
}

 

• arr: 전체 수열을 담은 배열
• cnt: 1부터 전체 수열의 최대값까지 등장 횟수를 저장할 배열
• 투포인터를 돌리면서, 조건에 맞는 경우 (K개 이하) 해당숫자 cnt 에 +1 을 한다.
• 조건에 맞지 않는 경우 left 를 땡겨오면서 해당 숫자의 cnt 를 -1 을 해준다.
• 매번 result 를 최대값으로 갱신해준다.