[백준] BOJ 20922 겹치는 건 싫어 (실버 1)

문제

---

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

20922번: 겹치는 건 싫어

---

해설

---

---

1. 처음에 수의 범위만큼 배열을 생성해둔다.
   해당 배열은 현재 수가 몇개 나왔는지 카운팅할 때 사용
2. 부분 수열을 확인할 때, 현재까지의 부분 수열에 현재 추가하려는 수가 K개보다 작게 있다면
   현재 수를 카운팅해주고, 부분 수열의 길이를 최대값에 업데이트한다.
3. 만약, 현재 추가하려는 수가 K개 만큼 부분수열에 들어있다면,
   왼쪽에서 가장 가까운 해당 수 다음부터 현재 추가하려는 수까지 부분 수열을 만들면
   현재 수를 추가하며 만들 수 있는 최대 길이의 부분 수열이다.
4. 따라서, 새롭게 만들어진 부분수열부터 다시 부분수열의 개수를 센다.

---

코드

---

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

public class Main {
    static StringBuilder sb = new StringBuilder();
    static int[] arr;
    static int N, K, max = 0;
    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());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        arr = new int[N];
        int[] numbers = new int[100001];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        int left = 0;
        for (int i = 0; i < N; i++) {
            if(numbers[arr[i]] != K){
                numbers[arr[i]]++;
                max = Math.max(max, i - left + 1);
                continue;
            }
            for (int j = left; j < i; j++) {
                if (arr[i] == arr[j]) {
                    left = j + 1; //다음 것 ~ i까지가 부분 수열
                    max = Math.max(max, i - left + 1);
                    break;
                }
                numbers[arr[j]]--;
            }
        }

        sb.append(max);
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

---

결론

---

해당 문제는 해결하지 못해서 친구의 풀이를 보고 이해했던 기억이 있다!.

현재까지 나온 수의 개수를 저장할 배열을 선언하고 입력받은 수를 인덱스로 사용하며

개수를 카운팅 해주는 테크닉이 아주 인상적이었던 문제!

---