[JAVA] 백준 13144 List of Unique Numbers_큐

 

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

 

접근 : 

 

 - 중복된 숫자가 나올 때까지 큐에 집어 넣는다.

 

 - 중복된 숫자가 나오면 큐에서 중복된 숫자가 나올때까지, 정답에 큐의 크기 만큼 더하고 큐에서 수를 하나씩 뺀다. 

 

 - 끝까지 도달하면 큐에 남은 사이즈(n)를 이용하여 나머지 계산( n*(n+1)/2 )을 하여 정답에 더한다.

 

 

 

코드구현 : 

 

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

public class Main {

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

        int n =  Integer.parseInt(br.readLine());

        String[] inputs = br.readLine().split(" ");
        int[] nums = new int[n];

        for(int i= 0 ; i < n ; i++) nums[i] = Integer.parseInt(inputs[i]);

        Set<Integer> visited = new HashSet<>();
        Queue<Integer> q = new LinkedList<>();

        long ans = 0;

        for(int j = 0 ; j < n ; j++){
            while(visited.contains(nums[j])){
                ans += q.size();
                visited.remove(q.poll());
            }
            q.offer(nums[j]);
            visited.add(nums[j]);
        }
        ans += (long) (visited.size() + 1) * visited.size()/2;

        System.out.println(ans);
        br.close();
    }
}