📙[Algo] BOJ13144. List of Unique Numbers

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

문제 요약

• 길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구하는 프로그램을 작성

시간 제한

• 1초

입력

• 첫 번째 줄에는 수열의 길이 N이 주어진다. (1 ≤ N ≤ 100,000)
• 두 번째 줄에는 수열을 나타내는 N개의 정수가 주어진다.
  • 수열에 나타나는 수는 모두 1 이상 100,000 이하이다.

출력

• 조건을 만족하는 경우의 수를 출력

접근법

• 먼저 정답 변수에 연속부분수열 길이가 1인 개수를 미리 더해줌
• 이후는 투포인터로 가능한 개수를 구하려고 했다.
  • s = 0, e = 1부터 시작
  • 여기서 e가 가리키는 숫자를 포함한 연속 부분 수열의 개수는 e보다 앞에 있는 숫자들의 개수에 영향을 받는다.
  • 즉, 문제의 조건을 충족한 범위 s와 e가 주어졌다면, e를 포함한 연속부분수열의 개수는 앞의 숫자 개수인 e - s만큼이된다.
  • 따라서 e를 이동시키며 가리키는 숫자 방문체크를 했고, 정답 변수에 e-s를 더해주었다.
  • 만약 e가 가리키는 숫자가 이미 방문했던 숫자라면 s를 늘리고, 기존에 s가 가리켰던 숫자 방문은 해제한다.
  • 위 로직을 e가 끝 숫자를 만날때까지 반복 수행

코드

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

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

        long answer = N;
        int s = 0, e = 1;
        visited[arr[s]] = true;
        while (e < N) {
            if (visited[arr[e]]) {
                visited[arr[s]] = false;
                s++;
            } else {
                visited[arr[e]] = true;
                answer += (e - s);
                e++;
            }
        }

        System.out.println(answer);
    }
}