백준 20922[자바] java 겹치는 건 싫어

문제 링크: https://www.acmicpc.net/problem/20922

20922번: 겹치는 건 싫어

▶문제

홍대 병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 K개 이하로 들어 있는 최장 연속 부분 수열의 길이를 구하려고 한다.

 100000 이하의 양의 정수로 이루어진 길이가 N인 수열이 주어진다.  이 수열에서 같은 정수를 K개 이하로 포함한 최장 연속 부분 수열의 길이를 구하는 프로그램을 작성해보자.

▶입력

첫째 줄에 정수 N (1≤N≤200000)과 K (1≤K≤100)가 주어진다.

둘째 줄에는 a1,a2,...an이 주어진다 (1≤ai≤100000)

▶출력

조건을 만족하는 최장 연속 부분 수열의 길이를 출력한다.

▶해설

투 포인터로 접근할 수 있는 문제입니다. 조건을 살펴보겠습니다. 

 

1. 같은 정수가 k개 이하로 포함되어야 한다.

2. 가장 긴 수열을 찾아라.

 

간단하게 접근할 수 있습니다.

 

변수 left, right를 정의하고, right의 해당하는 숫자의 개수가 k보다 작다면 개수에 +1을 해주고, right++를 해줘 다음 숫자를 받을 준비를 합니다.  

 

하지만 right에 해당하는 숫자의 개수가 k와 같다면, 다음 숫자를 더하면 k보다 커지게 되므로 left에 해당하는 숫자의 count를 줄이고 left++를 해줘 위치를 한 칸 앞으로 당겨옵니다. 

 

ex) n = 7 k = 2일 때 수열: 1 2 2 2 3 4 5

left = 0, right = 0;

1의 개수는 현재 0입니다. 따라서 0<2이므로 1의 개수를 1 개 늘려주고, right++를 합니다.

 

left=0, right = 1;

위와 동일

 

left= 0, right =2;

위와 동일

 

left =0, right =3

이때 k와 2의 개수가 같습니다. 따라서 left의 해당하는 1의 카운트 개수를 줄이고, left++을 해줍니다. 

하지만 2의 개수를 줄인 것이 아니라 1의 개수를 줄인 것이므로 2의 개수 < k를 만족할 때까지 left++은 계속됩니다.

 

따라서 아래와 같은 식이 만들어집니다. cnt는 숫자의 개수를 담고 있습니다. 

private static void two() {
    int left = 0;
    int right = 0;

    while(left<=right){
        if(right<=n-1 && cnt[arr[right]] < k){
            cnt[arr[right]]++;
            right++;
        }
        else if(cnt[arr[right]]==k){
            cnt[arr[left]]--;
            left++;
        }
        result = Math.max(right-left,result);

        if(right==n){
            return;
        }
    }
}

 

전체 코드

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


public class Main {

    static int n, k;
    static Map<String, Integer> map = new HashMap<>();

    static int[] arr;
    static int[] cnt;
    static int result;


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] s = br.readLine().split(" ");

        n = Integer.parseInt(s[0]);
        k = Integer.parseInt(s[1]);

        String[] s1 = br.readLine().split(" ");

        arr = new int[n];
        cnt = new int[100001];

        for(int i=0; i<s1.length; i++){
            arr[i] = Integer.parseInt(s1[i]);
        }
        two();

        System.out.println(result);
    }

    private static void two() {
        int left = 0;
        int right = 0;

        while(left<=right){
            if(right<=n-1 && cnt[arr[right]] < k){
                cnt[arr[right]]++;
                right++;
            }
            else if(cnt[arr[right]]==k){
                cnt[arr[left]]--;
                left++;
            }
            result = Math.max(right-left,result);

            if(right==n){
                return;
            }
        }
    }
}