[JAVA] 백준 20922번 : 겹치는 건 싫어

[20922번 : 겹치는 건 싫어] - Silver1

접근 방법 : 투 포인터, 해시맵 (코드 아래 설명 참고)

---

[ 문제 ]

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

 

 100,000 이하의 양의 정수로 이루어진 길이가 N인 수열이 주어진다. 

이 수열에서 같은 정수를 K개 이하로 포함한 최장 연속 부분 수열의 길이를 구하는 프로그램을 작성해보자.

---

[ 입력 ]

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

둘째 줄에는 a_1, a_2, ... a_n이 주어진다 1 ≤ a_i ≤ 100,000

---

[ 출력 ]

# 예제 입력 1
9 2
3 2 5 5 6 4 4 5 7

# 예제 출력 1
7

---

[ Code ]

import java.io.*;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.StringTokenizer;

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());
        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, right = 0, max = 0;
        HashMap<Integer, Integer> map = new LinkedHashMap<>();
        while (right < n) {
            if (map.getOrDefault(arr[right], 0) < k) {
                map.put(arr[right], map.getOrDefault(arr[right], 0) + 1);
                right++;
            } else {
                map.put(arr[left], map.get(arr[left]) - 1);
                left++;
            }

            max = Math.max(max, right - left);
        }

        bw.write(String.valueOf(max));
        bw.flush();
        bw.close();
    }
}

1. 입력

- 배열에 숫자를 넣어준다.

- 같은 정수가 몇개 들어 있는지 확인하기 위해 HashMap 사용

 

2. 투 포인터

- 해시맵에 들어있는 동일한 값의 value가 k보다 작다면 value+1 로 추가한다.

- right++

 

- value가 k보다 크다면 더이상 넣을 수 없다는 뜻이므로, left++하고 value-1한다.

 

3. max값 추출

- right - left 하면 몇 개가 포함되어 있는지 나온다.