[백준 20922번 / java] 겹치는 건 싫어

문제

20922번: 겹치는 건 싫어 (acmicpc.net)

같은 수가 K개 이하인 최장 연속 부분 수열의 길이의 최대값 구하기.

최장 연속 부분 수열 : 수열의 원소를 연속으로 하나 이상 선택한 부분수열

풀이

IDEA1)

1. start 인덱스 지정
2. start 인덱스부터 +1 하며 쭉 탐색, 해당 숫자가 몇 번 나오는지 체크하며 진행, 부분수열의 길이도 카운트해줌
3. 숫자가 K번 이상 중복해서 나왔으면 탐색을 멈춤
4. 해당 작업을 브루트 포스로 진행

-> 시간 초과. O(N^2) 인데 N은 최대 200,000이다.

O(N)의 시간복잡도를 가진 투포인터를 써야 한다.

 

IDEA2)

투포인터 사용

1. start, end 모두 배열의 첫 번째 원소를 가리키게 함

2-1. 현재 연속 부분 수열에 같은 숫자가 K개 이하이면 end를 1 증가시킴

2-2. 현재 연속 부분 수열에 같은 숫자가 K개 이상이면 start를 1 감소시킴

3. start, end의 증감에 따라 dup[] 의 원소 개수와 연속 부분 수열 길이 (length)도 함께 변경시켜준다.

4. lengh의 길이를 max와 비교하여 max 갱신

 

코드

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

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;

        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

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

        int max = Integer.MIN_VALUE;
        int start = 0, end = 0, length = 0;
        while(end < arr.length){
            if(dup[arr[end]] < K){
                dup[arr[end]]++;
                end++;
                length++;
            }else{
                dup[arr[start]]--;
                start++;
                length--;
            }
            if(max < length)
                max = length;
        }
        bw.write(max+" ");
        bw.close();


    }

}