Algorithm / 연속 부분 수열 합의 개수

문제

프로그래머스 / 연속 부분 수열 합의 개수

1) 문제 풀이

func solution(_ elements:[Int]) -> Int {
    var result: Set<Int> = []
    let round = elements + elements
    
    for i in 0..<elements.count {
        for j in 0..<elements.count {
            let num = round[j...(j + i)].reduce(0) { $0 + $1 }
            result.insert(num)
        }
    }
    
    return result.count
}

결과

2) 코드 개선

⚠️ 문제점 분석

• 슬라이싱round[j...(j + i)]
  • Array 슬라이싱은 내부적으로 ArraySlice를 만들어서 O(k) 시간이 걸림
  • 이게 중첩 반복문 안에 있어서 총 시간 복잡도가 O(n^3)이 됨
• 중첩 반복문
  • 바깥 i는 부분 수열의 길이 (1 ~ n)
  • 안쪽 j는 시작 인덱스 (0 ~ n-1)
  • 그 안에서 매번 reduce로 합을 계산 -> 총 연산량이 많음

✅ 개선 포인트

• 슬라이딩 윈도우 방식 활용
  • 합을 슬라이싱하고, reduce로 매번 계산하는 대신, 슬라이딩 윈도우를 사용해 누적 합을 O(1) 시간에 갱신

func solution(_ elements: [Int]) -> Int {
    var result = Set<Int>()
    let n = elements.count
    let doubled = elements + elements

    for length in 1...n {
        var sum = doubled[0..<length].reduce(0, +)
        result.insert(sum)

        for start in 1..<n {
            sum = sum - doubled[start - 1] + doubled[start + length - 1]
            result.insert(sum)
        }
    }

    return result.count
}

결과