[백준 / 골드4] 13144 List of Unique Numbers (Java)

문제 보기

사용한 것

• 연속한 수열 중에서 같은 수가 중복되지 않는 수열의 개수를 구하기 위한 투포인터

풀이 방법

• 기준 인덱스 l에서 r을 증가시키면서 같은 수가 중복되지 않는 수열의 개수를 구한다.
• 구간 l ~ r에서 연속한 수가 없었다면, 개수는 r - l - 1 이다.
• 연속한 수가 등장하거나 배열의 크기를 초과했다면 l을 1 증가시킨다.
• r까지의 인덱스는 중복되지 않음이 보장되기에 그대로 사용한다.

코드

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

        int l = 1;
        int r = 0;
        long answer = 0;
        int[] ct = new int[100_001];
        while (l <= n) {
            while (r + 1 <= n && ct[arr[r + 1]] == 0) {
                r++;
                ct[arr[r]]++;
            }

            answer += r - l + 1;
            ct[arr[l++]]--;
        }

        System.out.println(answer);
    }
}