[Kotlin][Algorithm] 13144 - List of Unique Numbers

D.O·2024년 3월 16일

문제 요약

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

문제 접근

처음에는 방법이 딱히 생각나지 않아서 브루트포스로 접근하였다.
대신 브루트포스로 접근하면 n이 100,000으로 당연하게도 시간 초과가 나기 때문에 최적화 해주는 방식으로 접근하였지만 1부터 100000 까지 가지치기를 할 수 없는 경우의 수 등에서 시간초과가 나는 것을 확인하였다.

두 포인터

문제 알고리즘을 구분을 봤는데 두 포인터이기 때문에 두 포인터로 접근하였다.

중복되는 숫자가 없어야 하므로 두 포인터로 중복되는 숫자가 있다면 start를 제거해주고 없다면 end를 추가하는 씩으로 진행하면된다.

이렇게 보면 매우 간단하나 중요한것은 중간에 연속된 부분 수열의 개수를 구하는 공식만 발견한다면 매우 쉽게 풀리는 문제이다.

수열에서 연속된 부분을 고려할 때, 특정 범위의 수들이 모두 다르다면, 그 범위 내에 속하는 모든 부분 수열은 유니크한 숫자의 집합을 가진다.

예를 들어, [1, 2, 3]이라는 부분 수열이 있다면, 가능한 유니크한 부분 수열은 [1], [2], [3], [1, 2], [2, 3], [1, 2, 3]으로 총 6개이다. 이는 부분 수열의 길이 n에 대해 n * (n + 1) / 2 공식으로 계산할 수 있는 경우의 수와 일치한다.
이는 모든 가능한 부분 수열의 수를 구하는 공식이며, 이 문제에서는 각 단계마다 유일한 부분 수열의 개수를 더하는 방식이 필요하다.

각 부분 수열을 보면

1 2

2 3

1 2 3

이런식으로 end 포인터가 증가될 때마다. 현재 포인터 사이의 거리 만큼의 개수가 생긴다.

이제 공식을 이용하면 된다.

코드


fun main() {
    val br = System.`in`.bufferedReader()
    val n = br.readLine().toInt()
    val arr = br.readLine().split(" ").map { it.toInt() }

    var start = 0
    var end = 0
    val set = hashSetOf<Int>()
    var answer = 0L
    while (end < arr.size) {

        if (!set.contains(arr[end])) {
            set.add(arr[end])
            answer += (end - start + 1)
            end++
        } else {
            set.remove(arr[start])
            start++
        }
    }

    println(answer)
}