[Swift] 연속된 부분 수열의 합 문제 풀이 [Programmers - Level2]

💬 문제

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

프로그래머스

 

---

💬 Idea

• 투포인터를 이용해서 풀이하자는 아이디어를 떠올려 풀이했다.
• 연속된 부분 수열의 합을 저장하는 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]
}