[ BOJ ][JAVA][13144] List of Unique Numbers

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

13144번: List of Unique Numbers

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	32 MB	811	318	239	41.493%

문제

길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구하는 프로그램을 작성하여라.

입력

첫 번째 줄에는 수열의 길이 N이 주어진다. (1 ≤ N ≤ 100,000)

두 번째 줄에는 수열을 나타내는 N개의 정수가 주어진다. 수열에 나타나는 수는 모두 1 이상 100,000 이하이다.

출력

조건을 만족하는 경우의 수를 출력한다.

예제 입력 1 복사

5
1 2 3 4 5

예제 출력 1 복사

15

예제 입력 2 복사

5
1 2 3 1 2

예제 출력 2 복사

12

예제 입력 3 복사

5
1 1 1 1 1

예제 출력 3 복사

5

코드

/*
    List of Unique Numbers
    투포인터
*/
import java.io.*;
import java.util.*;
public class p13144 {
    static int n;
    static int[] arr, cnt;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        arr = new int[n + 1];
        cnt = new int[100000 + 1];

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

        // "연속한" ~~ 수 -> 투포인터 접근해보자.
        tp();
    }

    static void tp() {
        long ans = 0;

        int lo = 1;
        int hi = 0;
        while (lo <= n) {
            // 현재 위치(lo)에서 시작해서 조건만족할때까지 hi를 늘려나간다
            while (hi + 1 <= n && cnt[arr[hi + 1]] == 0) {
                hi++;
                cnt[arr[hi]]++;
            }

            ans += hi - lo + 1;

            // lo를 한칸씩 밀면서 볼것이기 때문에 계산이 끝나고 나면 lo를 한 칸 밀어준다.
            // 이전 위치의 cnt는 다음번 계산에서 제외하기 위해 cnt[arr[lo]]--
            cnt[arr[lo++]]--;
        }
        System.out.println(ans);
    }
}