[13144] List of Unique Numbers

🔗 문제 링크

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

🔍 문제 설명

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

⚠️ 제한사항

• $(1 ≤ N ≤ 100,000)$

• 수열에 나타나는 수는 모두 1 이상 100,000 이하이다.

🗝 풀이 (언어 : Java)

투포인터 문제이고, 카운트하는 배열을 선언하는 것 까지는 생각해내서 풀었지만, 잘 풀리지 않았다. 문제의 연속에 대한 정의를 잘못 이해해서 right 포인터의 뒤의 포인터를 미리 체크하지 않고 +1하고 체크하는 로직을 짜서 실패했다. 문제의 요구를 올바르게 이해하면 생각보다 어렵지는 않다. 인덱스가 여러개 나와서 헷갈리는 것만 조심하자.

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

class Main {
    private static long findUniqueCase(int n, int[] nums) {
        long answer = 0;
        // 해당 수 등장했었는지 개수 표시하는 배열
        int[] check = new int[n + 1];
        // 다음 수를 확인하고 중복아닌 경우만 right 증가시키기 위해 -1로 초기화해 0부터 확인
        for (int left = 0, right = -1; left < n; left++) {
            // 다음 수가 중복이 아니면 right+1, check도 해당 수 카운트
            while (right < n - 1 && check[nums[right+1]] == 0)
                check[nums[++right]]++;
            // 반복문 탈출시, 정답 카운트하고 해당 left 숫자 등장 숫자에서 지우기
            answer += (right - left + 1);
            check[nums[left]]--;
        }
        return answer;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int[] nums = new int[n];
        for (int i = 0; i < n; i++)
            nums[i] = Integer.parseInt(st.nextToken());
        br.close();
        System.out.println(findUniqueCase(n, nums));
    }
}