자바(백준) 13144 List of Unique Numbers

오답 노트 & 새로 알게 된 점

문제에서 연속한 1개 이상의 수를 뽑았을 때 라는 말로 투 포인터 힌트를 줬다.

 

투 포인터를 구현하는 코드는 어렵지 않았지만 경우의 수를 계산할 때 생각이 필요하다.

 

1 2 3 1 2

에서 처음에 1에서 3까지 e가 이동할 수 있다.

 

그렇다면 경우의 수는

1

1 2

1 2 3

이 있다.

 

이 점을 보았을 때, e - s + 1를 하게 되면 경우의 수를 계산할 수 있다.

 

---

코드

package TwoPointers;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class BOJ13144 {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
 
    static int N;
    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));
 
        N = atoi(br.readLine());
 
        A = new int[N + 1];
 
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        for (int i = 1; i <= N; i++) {
            A[i] = atoi(st.nextToken());
        }
 
        pro();
    }
 
    static void pro() {
        int e = 0;
        long cnt = 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]] <= 0) {
                possible[A[++e]]++;
            }
 
            cnt += (e - s + 1);
        }
 
        System.out.println(cnt);
    }
}