[BOJ 20922] 겹치는 건 싫어 - java

백준 20922번: 겹치는 건 싫어

풀이

💡 두 개의 포인터를 사용하여, 가능한 경우를 탐색한다!

• int[] cnt = new int[100001] : 원소가 포함된 횟수를 담는다.
• int start = 0, end = 0 : 포인터 초기화
• if (cnt[arr[end]] < K) : end 번째 원소를 포함시켜도 K 이하인 경우
  • 해당 원소의 횟수 증가
  • end++
  • 수열의 길이 갱신
• else : end 번째 원소를 포함시킬 수 없는 경우 👉 end를 포함시킬 수 있을 때까지 start를 증가시킨다.
  

int start = 0, end = 0;
while (start < N && end < N) {
    if (cnt[arr[end]] < K) {
        cnt[arr[end]]++;
        end++;
        answer = Math.max(answer, end - start);
    } else {
        cnt[arr[start]]--;
        start++;
    }
}

전체 코드

package boj;

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

// 백준 20922번: 겹치는 건 싫어
public class BOJ_20922 {

    static int N, K;
    static int[] arr;
    static int[] cnt = new int[100001];
    static int answer;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        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 start = 0, end = 0;
        while (start < N && end < N) {
            if (cnt[arr[end]] < K) {
                cnt[arr[end]]++;
                end++;
                answer = Math.max(answer, end - start);
            } else {
                cnt[arr[start]]--;
                start++;
            }
        }
        System.out.println(answer);
    }
}