[백준 20922] 겹치는 건 싫어 (JAVA)

백준 20922번 문제 - 겹치는 건 싫어 

20922번: 겹치는 건 싫어

---

문제 분석

 

문제 분석

• 숫자 N개를 입력 받고, 숫자가 K이하로 중복되도록 최장 연속 부분 수열의 길이를 출력

---

해결 키 포인트

 

• 투포인트로 문제 풀이
• 중복 수 판단
  • 처음에 중복을 어떻게 알아낼까 고민함
    1. Map을 사용해서 중복되는 숫자가 있는지 확인
       맵은 입력숫자, 중복 개수로 판단 → 시간 초과(put, get을 많이해서 그런지..(?))
    2. 입력받을 수 있는 수가 100000까지니 100001개 배열 만들어서 중복 개수 확인 → 통과

---

코드

 

import java.io.*;
import java.util.ArrayList;
import java.util.List;
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 [] nums = new int [N];

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

        int result = 0;
        int start = 0, end = 0;
        int [] numsCount = new int[100001];

        while(end < N) {
            while (end < N && numsCount[nums[end]] < K) {
                numsCount[nums[end]]++;
                end++;
            }
            result = Math.max(result, end - start);
            numsCount[nums[start]]--;
            start++;
        }

        System.out.println(result);
    }
}