2003번: 부분합 - Kotlin (투포인터)

1806번: 부분합

문제

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

출력

첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

 

나의 풀이 - 1번째

 이 문제는 수열에서 연속된 수들의 부분합 중에 그 합이 S이상이 되는 수를 구하는 문제로 처음에 나는 DFS를 사용해서 구현하였다. 하지만 DFS를 사용할 때 수열의 모든 지점 부터 탐색해야 해서 O(N²)의 시간 복잡도로 인해 시간 초과가 나오고 말았다.

lateinit var array: IntArray
var result = 100000

fun main() = with(System.`in`.bufferedReader()) {
    val (n, s) = readLine().split(" ").map{ it.toInt() }
    array = readLine().split(" ").map { it.toInt() }.toIntArray()

    for (i in array.indices) {
        dfs(i, 1, array[i], s, n)
    }
    if (result == 100000)
        println(0)
    else
        println(result)
}

fun dfs(now: Int, depth: Int, cnt: Int, s: Int, n: Int) {
    if (cnt >= s) {
        result = result.coerceAtMost(depth)
    }
    if (now == n - 1) return
    dfs(now + 1, depth + 1, cnt + array[now + 1], s, n)
}

 

2번째 풀이

 2번째 문제를 풀 때 가장 중요했던 것은 반복문을 하나로 줄여 시간 복잡도를 O(N)으로 만드는 것이었다. 그러기 위해서는 투포인터 알고리즘을 사용해야 했다. 투포인터 알고리즘은 left 와 right같이 2개의 포인터를 두어 부분배열의 범위를 나타내 주는 방식이다. 이 문제는 sum이 지정된 최대 값보다 크거나 right 값이 배열의 최대 크기를 벗어나지 않는다면, right를 하나씩 증가시키면서 sum 값을 더해주고 만약 sum이 지정된 최대 값 이상이 되었다면 left를 증가시키고 범위에 합인 sum에서 빼준다. 

lateinit var array: IntArray
var result = 100000

fun main() = with(System.`in`.bufferedReader()) {
    val (n, s) = readLine().split(" ").map{ it.toInt() }
    array = readLine().split(" ").map { it.toInt() }.toIntArray()

    var sum = 0
    var left = 0
    var right = 0
    while (true) {
        if (sum >= s) {
            result = result.coerceAtMost(right - left)
            sum -= array[left++]
        }
        else if (right == n) break
        else sum += array[right++]
    }
    if (result == 100000) println(0)
    else println(result)
}