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

 

 

 

문제 출저

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

20922번: 겹치는 건 싫어

 

 

 

문제 풀이

수열이 주어질 때, 같은 정수를 K개 이하로 포함한 최장 연속 부분 수열의 길이를 구해야 한다. 

 

 

투 포인터로 문제를 풀었습니다.

end, start를 두 개의 포인터를 이용했습니다. end, start는 모두 0에서 시작합니다. 

end는 배열의 끝까지 탐색합니다. end 포인터에 걸린 숫자의 갯수를 +1 해줍니다. 

만약 숫자의 갯수가 K보다 크다면 start가 움직입니다. start의 숫자의 갯수를 -1 하면서 start의 값을 +1 합니다.

이 과정으로 숫자의 갯수가 K 이하가 되면 다시 end를 움직입니다.

이 과정을 반복하면서 start, end 길이를 업데이트하여 가장 큰 길이를 구하면 됩니다. 

 

 

 

소스 코드

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

/*
겹치는 건 싫어
https://www.acmicpc.net/problem/20922

코드가 간결해지는 방법으로는 int 배열을 사용하는 방법이 있다.
숫자의 범위가 100_000 이하이므로 100_000의 크기를 가진 int 배열에 나온 횟수를 저장하는 것이다.
 */

public class Main {

    static int n;
    static int k;
    static int[] board;

    static Map<Integer, Integer> counts;
    static List<Integer> overNumber;

    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());
        board = new int[n];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            board[i] = Integer.parseInt(st.nextToken());
        }

        int s = 0;
        int e = 0;

        counts = new HashMap<>();
        overNumber = new ArrayList<>();

        int answer = 0;

        while(s <= e) {

            int number = board[e];
            counts.put(number, counts.getOrDefault(number, 0) + 1);

            if(counts.get(number) > k) {
                overNumber.add(number);
            }

            while (check()){
                number = board[s];
                counts.put(number, counts.get(number) - 1);

                if(overNumber.contains(number)) {
                    if(counts.get(number) <= k) {
                        overNumber.remove(Integer.valueOf(number));
                    }
                }

                if(s < n) {
                    s++;
                }
                if (s == n) break;
            }

            answer = Math.max(answer, e - s + 1);

            e = Math.min(e+1, n - 1);

        }

        System.out.println(answer);


    }

    // 같은 정수가 k개 초과로 있는지 확인
    public static boolean check() {
        if (overNumber.isEmpty()) {
            return false;
        }
        return true;
    }

}