[BOJ 13144] List of Unique Numbers (Java, 투포인터)

 

 

---

문제 링크

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

13144번: List of Unique Numbers

---

풀이

- 투 포인트 기법과 카운팅 배열을 활용하여 1 ~ N 까지의 모든 경우의 수 합을 더하면 됨 

- 시간복잡도 O(N)

 

이때 최대값의 경우 

1	2	3	...	100,000
1	2	3	...	100,000

1 ~ 100,000까지의 합을 나타내기 때문에 100000(99999) / 2 = 대략 50억이기 때문에 long으로 풀이 해야 함

 

L = 1인 경우 100,000

L = 2인 경우 99,999

L = 3인 경우 99,998

...

L = 100,000 인 경우 1

---

제출 코드

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

public class Main {
   
    static int N;

    static int[] NUMBERS;

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

        NUMBERS = new int[N + 1];
        st = new StringTokenizer(br.readLine());
        for(int i = 1; i <= N; i++) {
            NUMBERS[i] = Integer.parseInt(st.nextToken());
        }
    }

    static void pro() {
        int[] cnt = new int[100001];

        int L = 1, R = 1;
        long ans = 0L;
        while(L <= N) {
            while(R <= N && cnt[NUMBERS[R]] == 0) {
                cnt[NUMBERS[R]] += 1;
                R += 1;
            }

            ans += (R - L);

            cnt[NUMBERS[L]] -= 1;
            L += 1;
        }

        System.out.println(ans);
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
}