#1806 부분 합

문제

---

 

코드

---

import kotlin.math.min

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

    var min = Int.MAX_VALUE
    var start = 0
    var end = 0
    var sum = 0

    while (end <= n) {
        if (sum >= s) {
            min = min(min, end - start)
            sum -= seq[start]
            start++
        } else {
            if (end == n) break
            sum += seq[end]
            end++
        }
    }
    println(if (min == Int.MAX_VALUE) 0 else min)
}

 

풀이

---

일반적인 반복문으로는 O(n^2)의 시간복잡도를 가지는데 n이 100,000 까지라서 이 방법은 무리라고 생각했다.

 

투 포인터 알고리즘을 사용하면 해당 문제를 O(n) 시간복잡도로 해결할 수 있다.

 

투 포인터 알고리즘이란?
배열이나 리스트에서 두 개의 포인터를 사용해 특정 조건을 만족하는 부분 구간을 효율적으로 탐색하는 알고리즘
일반적으로 배열이나 리스트가 정렬되어있을 때 사용한다.

 

1. 처음 시작할 땐 두 개의 포인터 start, end를 0으로 설정한다.

2. start 부터 end 범위의 수열의 합이 s 보다 크다면 count를 1 증가시키고, start를 1 증가

3. start 부터 end 범위의 수열의 합이 s 보다 작다면 end를 1 증가

주어진 수열을 전부 탐색할 때 까지 2 ~ 3번을 반복한다.

 

처음에는 start 부터 end 범위의 수열의 합을 구하는 데 subList를 사용했다.

그래서 그런지 시간초과가 발생했다.

 

그래서 반복문을 지날 때 마다 이전 sum 값에 추가된 수는 더해주고, 빠진 수는 빼도록 했다.

이렇게 구현하니 해결되었다~

 

투 포인터 알고리즘은 처음 풀어보는데, 간단하지만 의외로 종료 조건이나 이런 부분에서 머리를 써야하는 것 같다.

 

 

 

참고

---

 

https://butter-shower.tistory.com/226

[Algorithm] 투포인터(Two Pointer) 알고리즘

https://adjh54.tistory.com/384

[Java/알고리즘] 투 포인터 알고리즘(Two Pointer Algorithm) 이해하기 -1 : 종류, 활용방안