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

20922 겹치는 건 싫어 문제 링크

문제

#1

import java.awt.*;
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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        int Index = 0;
        for(int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            Index = Math.max(Index, arr[i]);
        }
        int[] countArr = new int[Index];

        int start = 0;
        int end = 0;
        int answer = 0;
        int count = 0;
        while (end != N-1) {
            countArr[arr[end]-1]++;
            if(countArr[arr[end]-1] > K) {
                start = end;
                countArr = new int[Index];
                answer = Math.max(answer, count);
                count = 0;
            } else if (countArr[arr[end]-1] <= K) {
                end++;
                count++;
            }
        }

        bw.write(answer+"");
        bw.flush();
        bw.close();
    }
}

• 반례
  
• 지금 코드는 같은 숫자가 K만큼 나오면 마지막 인덱스 뒤부터 count하기 시작함
• 반례를 살펴보면 같은 숫자가 K만큼 나오면 첫 인덱스 뒤부터 count해야 한다는 것을 알 수 있음

#2

• for문으로 첫 인덱스를 구하도록 함
• 이렇게 하면 O(N)이 아닌건가..?

import java.awt.*;
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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        int Index = 0;
        for(int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            Index = Math.max(Index, arr[i]);
        }
        int[] countArr = new int[Index];

        int start = 0;
        int end = 0;
        int answer = 0;
        int count = 0;
        while (end != N) {
            countArr[arr[end]-1]++;
            if(countArr[arr[end]-1] > K) {
                for(int i=start; i<end; i++) {
                    if(arr[i] == arr[end]) {
                        start = i+1;
                        end = start;
                        break;
                    }
                }
                countArr = new int[Index];
                answer = Math.max(answer, count);
                count = 0;
            } else if (countArr[arr[end]-1] <= K) {
                end++;
                count++;
            }
        }
        answer = Math.max(answer, count);

        bw.write(answer+"");
        bw.flush();
        bw.close();
    }
}

• 일단 맞기는 했는데..

블로그 참고

• 확실히 이쪽이 투 포인터를 사용했다고 하기 적합할..? 풀이긴 하다