[Algorithm] 연속된 부분 수열의 합

[hwangJi-dev]

💬 문제

https://school.programmers.co.kr/learn/courses/30/lessons/178870

💬 Idea

• 처음엔 연속된 부분 수열의 개수 라는 dp 문제와 유사하다고 생각되어 dp를 이용해서 풀이해주었다.
  그런데 시간 초과가 발생했다.

💬 풀이

import Foundation

func solution(_ sequence:[Int], _ k:Int) -> [Int] {
    var dp = Array(repeating: 0, count: sequence.count + 1)
    dp[0] = sequence[0]
    
    var ans: [[Int]] = []
    for i in 1..<sequence.count {
        dp[i] = dp[i - 1] + sequence[i]
        
        if dp[i] != k {
            var sum = dp[i]
            for j in 0..<i {
                sum -= sequence[j]
                if sum == k {
                    ans.append([j + 1, i])
                    break
                }
            }
        } else {
            ans.append([0, i])
        }
    }
    
    ans = ans.sorted(by: {
        if $0[1] - $0[0] == $1[1] - $1[0] {
            return $0[0] < $1[0]
        } else {
            return $0[1] - $0[0] < $1[1] - $1[0]
        }
    })
    
    return ans[0]
}

💬 Idea2

• 따라서 투포인터를 이용해서 풀이하자는 아이디어를 떠올려 풀이를 수정했다.
• 연속된 부분 수열의 합을 저장하는 sum 변수를 두고,
  • 현재 누적합이 k보다 작거나 같다면 p2(right)를 1씩 증가
    • p2를 증가시키면서 수열을 늘리기 때문에 p2를 증가시키고 누적합에다 p2 원소만큼을 더해줌.
  • 현재 누적합이 k보다 크다면 p1(left)를 1씩 증가
    • p1을 증가시키면서 수열을 좁히기 때문에 누적합에서 p1 원소만큼을 빼주고 p1을 증가시킴.
• 합이 k인 부분 수열이 여러 개인 경우 길이가 짧은 수열을 찾고, 길이가 짧은 수열이 여러 개인 경우 앞쪽(시작 인덱스가 작은)에 나오는 수열을 찾기 위해 정렬한다.
  • [시작 인덱스, 끝 인덱스]를 기준으로 끝 인덱스에서 시작인덱스를 뺀 값이 작은 순서대로 정렬한다.
  • 이 때 끝 인덱스에서 시작인덱스를 뺀 값이 같다면, 시작 인덱스가 작은 순대로 정렬한다.

💬 풀이

import Foundation

func solution(sequence:[Int], k:Int) -> [Int] {
    var sum = sequence[0]
    var p1 = 0
    var p2 = 0
    var ans: [[Int]] = []
    
    while p1 < sequence.count && p2 < sequence.count {
        if sum == k {
            ans.append([p1, p2])
        }
        
        if sum <= k {
            p2 += 1
            if p2 == sequence.count { break }
            sum += sequence[p2]
        } else {
            sum -= sequence[p1]
            p1 += 1
        }
    }
    
    ans = ans.sorted(by: {
        if $0[1] - $0[0] == $1[1] - $1[0] {
            return $0[0] < $1[0]
        } else {
            return $0[1] - $0[0] < $1[1] - $1[0]
        }
    })
    
    return ans.isEmpty ? [] : ans[0]
}