[백준] 13144: List of Unique Numbers - JAVA

in Algorithm on 기타

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

풀이

길이 N의 수열에서 연속한 1개 이상의 수을 뽑았을 때 같은 수가 여러번 등장하지 않는 경우의 수를 구해야 한다.

처음에는 첫번째 원소부터 시작하여 dfs탐색을 통해 구하려고 했었다.

방문체크는 비트마스킹을 이용할 계획이었다. 하지만 N의 범위와 숫자들의 범위가 커서 안되는 것을 깨달았다.

따라서 투포인터 알고리즘을 떠올렸다.

start, end를 0에서 부터 시작하여 방문처리를 하면서 end값을 증가시킨다.

이전에 나온 숫자가 나올때까지 end값을 증가시키고 ans에 end - start를 더해준다.

현재 start값에 대한 경우의 수를 구했으므로 현재 start값의 방문처리를 지우고 start값을 1늘려 다시 판단한다.

메모리: 25460KB

시간: 308ms

언어: Java 11

코드

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

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());
        int[] arr = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        long ans = 0;
        boolean[] visit = new boolean[100001];
        int end = 0;
        for (int start = 0; start < N; start++) {
            while (end < N && !visit[arr[end]]) {
                visit[arr[end]] = true;
                end++;
            }
            ans += end - start;
            visit[arr[start]] = false;
        }

        System.out.println(ans);
    }

}