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

in Algorithm on 기타

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

풀이

같은 원소가 K개 이하로 들어있는 최장 연속 부분 수열의 길이를 구해야한다.

원소의 개수를 세줄 배열을 만들어놓고

0부터 시작하여 원소의 개수를 세준다.

i번째 원소의 개수가 K개보다 크다면 start부터 시작하여 i번쨰 원소와 같은 원소가 나올때까지 count 배열에서 하나씩 빼준다.

(i - start + 1)이 조건을 만족하는 부분 수열의 길이이다.

최댓값과 비교하여 갱신해준다.

메모리: 32740KB

시간: 360ms

언어: Java 11

코드

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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[] count = new int[100001];
        count[arr[0]]++;
        int ans = 1;
        int left = 0;
        for (int i = 1; i < n; i++) {
            count[arr[i]]++;
            if (count[arr[i]] > k) {
                for (int j = left; j < i; j++) {
                    count[arr[j]]--;
                    if (arr[i] == arr[j]) {
                        left = j + 1;
                        break;
                    }
                }
            }

            ans = Math.max(ans, i - left + 1);
        }

        System.out.println(ans);
    }

}