[백준/Java] 13144 List of Unique Numbers

문제 분석

해당 문제를 가장 쉽게 풀려면 모든 경우를 다 확인해 보는 방법이다. 해당 알고리즘의 시간복잡도는 O(N^3)이므로(L 움직임 O(N), R 움직임 O(N), 중복 체크 O(N)) 시간을 초과하게 되어 최적화가 필요하다. 최적화 방법으로는 투포인터와 Count 기록 방법을 활용하겠다. 투포인터를 통해 Left와 Right를 움직이는 시간복잡도를 O(N)으로 줄이고 방문을 기록하여, 중복의 유무를 일일히 체크하는 것이 아닌 배열을 통해 한번에 알 수 있으므로 O(1) 만큼 걸린다. 따라서 이 방법대로 풀이하면 시간복잡도는 O(N)안에 문제를 해결할 수 있어 해당 방법으로 문제를 풀었다.

주의할 점은 Scanner를 사용하면 메모리가 초과된다는 점이다. BufferReader에 비해 시간이 오래걸린다는 것은 알았지만, 공간 복잡도에서도 손해를 보는 지는 이제 알게되었다.

 

문제 풀이

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

public class Main {

    static int N;
    static long count;
    static int[] numbers;
    static boolean[] isUsed;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        numbers = new int[N];
        isUsed = new boolean[100001];

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

        countNumberOfCases();

        System.out.println(count);
    }

    public static void countNumberOfCases() {
        for(int left = 0, right = -1; left < N; left++) {
            while (right + 1 < N && !isUsed[numbers[right + 1]]) {
                right++;
                isUsed[numbers[right]] = true;
            }

            count += right - left + 1;

            isUsed[numbers[left]] = false;
        }
    }
}