[백준][Java] 13144번 List of Unique Numbers

문제

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

 

코드

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

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[] nums = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        int left = 0;
        int right = 0;
        long answer = 0;

        Set<Integer> map = new HashSet<>();

        while (right < N) {

            while (map.contains(nums[right])) {
                map.remove(nums[left++]);
            }

            map.add(nums[right++]);
            answer += (right - left);
        }

        System.out.println(answer);
    }
}

 

풀이

1. 투포인터 개념 적용

• left, right 포인터를 이용하여 연속 구간을 관리
• right를 확장하며 중복이 없는 값을 Set에 추가
• 중복 값이 나오면 left를 증가시키며 중복이 제거될 때까지 Set에서 제거

2. 정답 계산 핵심( answer += right - left 인 이유)

• 매 순간 right가 가리키는 인덱스를 포함한 중복 없는 구간의 개수는 (right - left)
• 즉, 현재 시점에서 끝나는 모든 유효 구간의 개수를 한 번에 세는 방식

• 예를 들어 nums = [1, 2, 3]인 경우:
  • 가능한 중복 없는 연속 부분 수열은 [1], [1,2], [1,2,3], [2], [2,3], [3] → 총 6개
• 이 중 right가 2일 때 (값 = 3), left가 0이라면:
  • 끝이 right인 부분 수열은 [1,2,3], [2,3], [3] → 총 3 = right - left + 1개
  • right++ 이후이므로 실제 누적은 right - left

 

출력결과