[백준]#13144 List of Unique Numbers

문제

길이가 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

풀이

이 문제는 투 포인터를 이용해서 풀 수 있었다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;

public class Main {

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        String[] input = br.readLine().split(" ");
        int[] arr = new int[N];

        for(int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(input[i]);
        }
        long ans = 0;

        HashSet<Integer> visited = new HashSet<>();   //숫자 체크할 해쉬셋
        int left = 0;
        int right = 0;

        while(true) {
            if(right==N) {
                if(left==N) break;

                else {
                    ans += (right-left);
                    left++;
                }
            }

            else if(!visited.contains(arr[right])) {    //포함안된 숫자면 포인터 늘림
                visited.add(arr[right]);
                right++;
            }

            else {
                ans += (right-left);          //이미 포함된 숫자면 다 더해주고 시작 idx 늘림
                visited.remove(arr[left]);
                left++;
            }
        }

        System.out.println(ans);
    }
}