[Gold IV][JAVA]백준 13144번:List of Unique Numbers

문제 바로가기 > [Gold IV]백준 13144번:List of Unique Numbers

분류

• 두 포인터

풀이

• 문제에서 연속한 1개 이상의 수를 뽑았을 때 => 연속합은 투 포인터이다!
• 구간 start ~ end에서 연속한 수가 없었다면, => 경우의 수는 end - start이다.

부분 수열의 길이가 경우의 수가 되는 이유는 부분 수열의 길이는 해당 부분 수열이 포함하는 숫자의 개수를 의미합니다. 예를 들어, 연속한 부분 수열 (1, 2, 3)의 길이는 3입니다. 즉, 각 부분 수열의 길이를 경우의 수로 간주됩니다.

주어진 예제 입력 1 2 3 4 5의 경우를 살펴보겠습니다.
1. 길이가 1인 부분 수열: 1, 2, 3, 4, 5 (총 5개)
2. 길이가 2인 부분 수열: (1, 2), (2, 3), (3, 4), (4, 5) (총 4개)
3. 길이가 3인 부분 수열: (1, 2, 3), (2, 3, 4), (3, 4, 5) (총 3개)
4. 길이가 4인 부분 수열: (1, 2, 3, 4), (2, 3, 4, 5) (총 2개)
5. 길이가 5인 부분 수열: (1, 2, 3, 4, 5) (총 1개)

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int[] arr;
    static int[] cnt = new int[100000 + 1];

    public static void main(String arg[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        arr = new int[N];

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

        pro();
    }

    static void pro() {
        long res = 0;
        int start = 0, end = 0;

        while (start < N) {
            while (end < N && cnt[arr[end]] == 0) {
                cnt[arr[end]]++;
                end++;
            }
            res += end - start;

            cnt[arr[start]]--;
            start++;
        }
        System.out.println(res);
    }
}