자바(백준) 20922 겹치는 건 싫어

오답 노트 & 새로 알게 된 점

투 포인터 공부를 하고 있어서 이 문제는 무조건 투 포인터로 풀어야한다는 생각을 버리고 풀었다.

 

처음에 접근할 때, O(N^2)로 풀면 바로 TLE가 나기 때문에 아마 O(NlogN)이하로 풀어야한다.

그리고 연속 부분 수열의 길이라는 힌트를 줬기 때문에 투 포인터로 접근할 수 있다.

 

여기서 아마 중복 처리를 어떻게 해줬냐가 중요한 것 같다.

possible이라는 배열을 만들어 A[i] 배열의 value들을 index에 넣어 ++ 해주었다.

그 중 K값을 넘지 않게 탐색하면서 길이의 최댓값을 구해주면 된다.

 

---

코드

package TwoPointers;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class BOJ20922 {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static int N, K;
    static int A[];
    static int possible[] = new int[100001];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = atoi(st.nextToken());
        K = atoi(st.nextToken());
 
        A = new int[N + 1];
 
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            A[i] = atoi(st.nextToken());
        }
 
        pro();
    }
 
    static void pro() {
        int e = 0, len = 0;
 
        for (int s = 1; s <= N; s++) {
            if(possible[A[s-1]] > 0) possible[A[s-1]]--;
 
            while(e+1 <= N && possible[A[e+1]] < K){
                possible[A[++e]]++;
//                System.out.println(e);
            }
 
            len = Math.max(len, e - s + 1);
//            System.out.println(s + " " + e);
        }
 
        System.out.println(len);
    }
}