[백준] 13144 List of Unique Numbers (JAVA)

문제 링크:

13144번: List of Unique Numbers

 

 

난이도: 골드 4

 

 

문제:

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

 

 

입력:

첫 번째 줄에는 수열의 길이 N이 주어진다. (1 ≤ N ≤ 100,000)

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

 

 

출력:

조건을 만족하는 경우의 수를 출력한다.

 

문제 이해:

문제 이해는 어렵지 않다.

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

쉽게 예제 입력 2를 통해 왜 12인지 알아보자.

즉 처음부터 순차로 증가하면서 같은 수가 나올때 왼쪽 포인터를 이동시켜 다음 숫자를 기준으로 처음부터 다시 탐색하면 된다.

 

 

구현 방향:

이는 연속된 수열을 다루는 문제로, 투 포인터 알고리즘을 활용해 해결할 수 있다.
왼쪽(L)과 오른쪽(R) 포인터를 설정한 뒤,
연속된 수열이 유지되는 동안은 오른쪽 포인터를 이동시키며 구간을 확장한다.
만약 중복된 숫자가 나타나면, 왼쪽 포인터를 한 칸 이동시켜 중복을 제거하고 다시 탐색을 이어간다.

이때 HashSet을 사용하면 중복 여부를 빠르게 확인할 수 있어 시간 복잡도를 효율적으로 줄일 수 있다.

이를 코드로 그대로 구현하면 다음과 같다.

 

 

정답 코드:

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

public class Main {
    static int N;
    static int [] progression; //수열 배열


    public static long solve() {
        long result = 0;
        int L = 0;
        Set<Integer> set = new HashSet<>();

        for (int R = 0; R < N; R++) {
            // progression[R]가 중복이면, 중복이 해소될 때까지 L을 이동하며 제거
            while (set.contains(progression[R])) {
                set.remove(progression[L]);
                L++;
            }
            set.add(progression[R]);
            // R을 끝으로 하는 유효 구간 수 = (R - L + 1)
            result += (R - L + 1);
        }
        return result;
    }

    public static void main(String[] args) throws IOException {
        //초기 세팅
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        N=Integer.parseInt(br.readLine());

        progression=new int[N];

        StringTokenizer st=new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            progression[i]=Integer.parseInt(st.nextToken());
        }
        //초기 세팅 끝

        //탐색
        long result = solve();

        //결과 출력
        System.out.println(result);

    }
}

 

 

 

마무리하며:

처음에는 HashSet이 아닌 List를 사용했다.
인덱스를 옮길 때마다 원소를 추가하고, 중복이 발생하면 clear()를 호출해 다시 탐색을 시작했다.
하지만 이 방식은 문제가 많았다.

 

List.contains()는 내부적으로 매번 모든 원소를 순회하며 중복 여부를 검사한다.
즉, 한 번의 검사마다 O(N)의 시간이 걸렸고, 이 과정을 반복하면서 전체 연산량이 O(N²) 수준까지 늘어났다.
게다가 매번 새로운 Integer 객체가 생성되고, clear()로 비워도 메모리는 즉시 반환되지 않아 GC(가비지 컬렉션) 부하와 힙 메모리 사용량이 급격히 증가했다.
결국 이런 비효율적인 탐색 구조와 객체 생성이 겹치면서 메모리 초과가 발생했다.

 

이때 깨달았다. 중복 검사는 순차 탐색이 아닌 HashSet의 해시 기반 O(1) 탐색으로 처리했어야 했다.
또한 부분 수열의 개수를 단순히 result++로 누적하는 게 아니라,
투 포인터로 구간의 길이를 고려해 (R - L + 1) 방식으로 계산했어야 했다.

 

여러 문제를 풀어왔지만, 시간 복잡도와 메모리 효율을 고민하는 것이 매우 어려운 것 같다.

 

 

감사합니다.