[JAVA] [투포인터] 백준 13144 List of Unique Numbers

문제

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

13144번: List of Unique Numbers

코드

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

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

        int n=Integer.parseInt(br.readLine());
        int[] arr=new int[n];
        long answer=0;

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

        // 투 포인터
        int end=0;
        boolean[] visited=new boolean[100001];
        for(int i=0; i<n; i++){
            while(end<n && visited[arr[end]]==false){
                visited[arr[end]]=true;
                end++;
            }
            visited[arr[i]]=false;
            answer+=(end-i);

        }

        System.out.println(answer);
    }
    
}

시간복잡도

O(n)

 

어려웠던 점

문제 조건상 answer이 int 범위를 벗어나는 것을 늦게 알아차려 해결하는데 시간이 걸렸다.