[백준] 13144) List of Unique Numbers - Gold 4

[jusung-c]

문제 링크

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

문제 조건

• 길이가 N인 수열 (1 ≤ N ≤ 100,000)
• 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수
• 수열에 나타나는 수는 모두 1 이상 100,000 이하

---

아이디어

정답의 최대치를 먼저 계산해보면 10만개의 수가 모두 다른 수일 경우이다.
크기 1: N개
크기 2: N-1개
...
크기 N: 1개

즉, N + (N-1) + ... + 1 로 약 50억이다. int 범위를 초과하므로 long을 사용해야 한다.

방법 1) 가장 단순하지만 오래걸리는 방법
포인터 L, R을 이용해 L일 때 가능한 R의 경우를 모두 카운트한다. 2중 for문으로 시간 안에 풀이가 불가능하다.

방법 2) 투 포인터 방법

1. L, R 포인터를 첫번째 원소부터 시작한다.
2. 수가 중복되지 않는 지점까지 R을 이동한다.
3. 이미 존재하는 수가 나왔을 경우 R-L+1 만큼 cnt를 더해주고 L 포인터를 하나 이동한다.
4. 위 과정을 L 포인터가 배열의 끝에 도달할 때까지 반복한다.

---

시간 복잡도

L과 R이 N까지 이동하므로 O(N)이다. 시간 안 풀이가 가능하다.

---

구현

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader br;
    static StringTokenizer st;
    static int N;
    static int[] arr;

    public static void init() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

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

    }

    private static void pro() throws IOException {
        int R = 0;
        int[] cnt = new int[100001];
        long ans = 0;

        for (int L = 1; L <= N; L++) {
            cnt[arr[L - 1]]--;

            while (R + 1 <= N && cnt[arr[R + 1]] == 0) {
                R++;
                cnt[arr[R]]++;
            }

            ans += R - L + 1;
        }

        bw.write(ans + " ");

    }

    public static void main(String[] args) throws Exception {
        init();

        pro();

        bw.close();
    }
}