[투포인터] 백준 20922 겹치는 건 싫어

 

20922번: 겹치는 건 싫어

 

시간초과 코드

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

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        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];
        int[] check = new int[100001];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        int start = 0;
        int end = 1;
        int count = 1;
        int max = 0;
        check[arr[start]]++; 
        while(true) {
        	check[arr[end]]++; 
        	if(check[arr[end]] <= k) {
        		end++;
        		count++;
        		max = Math.max(count, max);
        	}
        	else if(check[arr[end]] > k) { //예외 
        		start=end+1;
        		max = Math.max(count, max);
        		count=1;
        		
        	}
        	if(end==n-1 || start==n-1) break;
        }
        System.out.println(max);
    }
}

각 숫자가 등장한 횟수를 체크하는 check 배열 사용.

IDE에서는 잘 나왔지만 시간초과가 발생했다. 시작점인 start를 불필요하게 갱신하며, end의 범위 설정에 문제가 있다.

 

 

개선된 코드(투포인터)

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

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        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];
        int[] check = new int[100001];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        int start = 0, end = 0, max = 0;
        while(end < n) {
            if(check[arr[end]] < k) {
                check[arr[end]]++;
                end++;
            } else {
                
                check[arr[start]]--;
                start++;
            }
            max = Math.max(max, end - start);
        }
        System.out.println(max);
    }
}

현재 end 위치의 숫자가 k번을 초과하면, start 위치의 숫자 등장 횟수를 줄이고 start를 오른쪽으로 이동시킨다.

그리고 end-start로 수열의 최대 길이를 갱신시켜줌.