[Swift 알고리즘] 백준 1806 부분합

△ 

투 포인터, 누적 합 Gold 4

백준 1806 부분합

문제
10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다.
이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.
출력
첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

부분합의 합이 S 이상이 되는 것들 중에서, 가장 짧은 부분합의 길이를 구하는 문제.

 

내 답안 - 76292 KB, 44ms

누적 합을 먼저 구해준 후, 투 포인터를 이용한 누적 합의 차이로 결과값을 구해주는 방식

1. 누적 합을 먼저 구해준다.

2. nums 배열의 총 합이 S 보다 작을 경우, 조건을 만족하는 부분합은 없으므로 0을 반환 (예외처리)

3. 0에서 시작하는 포인터 두 개를 사용하여 right 포인터가 n 이 될때까지

3-1. 부분합이 S 보다 작을 경우, right 포인터를 1씩 증가시키며 부분합을 늘려주고

3.-2. 부분합이 S보다 크거나 같을 경우, 조건을 만족하기 때문에 부분합 길이의 최소값을 업데이트 해주고, left 포인터를 1씩 증가시키며 부분합의 길이를 줄여준다. 

let ns = readLine()!.split(separator: " ").compactMap { Int($0) }
let nums = readLine()!.split(separator: " ").compactMap { Int($0) }

print(subsequence(n: ns[0], s: ns[1], nums: nums))

func subsequence(n: Int, s: Int, nums: [Int]) -> Int {
    var prefixSum = Array(repeating: 0, count: n+1)
    var result = n
    var left = 0, right = 0
    // 1
    for i in 1...n {
        prefixSum[i] = nums[i-1] + prefixSum[i-1]
    }
    // 2 예외처리
    if prefixSum[n] < s { return 0 }
    // 3
    while right <= n {
        if prefixSum[right] - prefixSum[left] < s { // 3-1
            right += 1
        } else { // 3-2
            result = min(right - left, result)
            left += 1
        }
    }

    return result
}

 

다른 답안 - 76292 KB, 44ms

누적 합을 따로 먼저 구하지 않고, 투 포인터를 사용하여 하나의 반복문 내에서 부분합과 조건을 만족하는 부분합의 최소 길이를 동시에 구해주는 방식

1. 부분합 sum 을 주어진 수열의 첫번째 인자로 초기화 해준다.

2. 0에서 시작하는 포인터 두 개를 생성

3-1. 부분합이 S 보다 작을 경우, right 포인터를 1 증가시키고 부분합 sum 에 다음 인덱스 수(nums[right])을 더해준다.

3-2. 부분합이 S 보다 크거나 같을 경우,

  a) 조건을 만족하기 때문에 부분합 길이의 최소값을 업데이트 해주고

  b) 부분합 sum 의 첫번째 수를 빼준 후

  c) left 포인터를 1 증가시킨다. 

4. 탈출 조건 : right 포인터가 n 과 같아질 때 반복문을 탈출한다. 

print(subsequence(n: 10, s: 15, nums: [5,1,3,5,10,7,4,9,2,8])) //2
print(subsequence(n: 10, s: 55, nums: [5,1,3,5,10,7,4,9,2,8])) //0
print(subsequence(n: 10, s: 54, nums: [5,1,3,5,10,7,4,9,2,8])) //10

func subsequence(n: Int, s: Int, nums: [Int]) -> Int {
    var sum = nums[0]  // 1
    var result = n + 1
    var left = 0, right = 0  // 2

    while true {
        if sum < s {  // 3-1
            right += 1
            if right == n { break }  // 4 탈출조건
            sum += nums[right]
        } else {  // 3-2
            result = min(result, right - left + 1)
            sum -= nums[left]
            left += 1
        }
    }

    return result == n + 1 ? 0 : result
}

이 방법에서 탈출조건을 따로 설정해주는 대신 while right < n { ... } 으로 반복문의 조건을 설정해줄 경우, nums[right] 에서 인덱스 에러가 날 수 있기 때문에 nums 의 마지막에 append(0) 을 해주고 풀어도 상관은 없다. 

 

후기 

투 포인터의 개념을 익히기에 아주 좋은 문제인 것 같다. 

누적합을 구해준 후에 투 포인터로 부분합의 길이를 구해주는 첫번째 방식이 처음에는 52ms 가 나오길래, 더 빠른 방법을 찾다가 두번째 방법을 시도해보았는데 한번에 모든 걸 처리하려다보니 좀 헷갈리더라. 

시간에는 큰 차이가 없지만 첫번째 방식이 훨씬 직관적이고 덜 혼란스럽게 문제를 풀 수 있는 것 같았다. 

혹시나 해서 같은 답으로 다시 제출해보니 44ms가 나옴,, 뭐야;; 그럼 시간상으로도 차이가 없다는건가? 

그렇다면 좀 더 직관적이고 쉽고 실수할 확률이 적은 첫번째 방식으로 문제를 푸는 것이 나을듯.