[프로그래머스/Swift] 134239번 - 우박수열 정적분

🔗 문제 링크

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

💡 구현 아이디어

1. 구간 구하기(1만들기)
2. 각 구간의 넓이 구하기
3. 요구하는 범위에 맞게 결과 구하기

💻 코드

import Foundation

func solution(_ k:Int, _ ranges:[[Int]]) -> [Double] {
    
    var result: [Double] = [] // 최종 구간 넓이
    var paths: [Int] = [] // 1로 만드는 순서
    var sizes: [Double] = [0] // 각 구간의 넓이
    var k = k
    
    // 1로 만들기
    while k > 1 {
        paths.append(k)
        if k % 2 == 0 { k = k / 2 }
        else { k = k * 3 + 1 }
    }
    paths.append(k)
    
    // 넓이 누적 합
    for idx in 1..<paths.count {
        let minN = Double(min(paths[idx], paths[idx-1]))
        let maxN = Double(max(paths[idx], paths[idx-1]))
        
        let value = (minN + maxN) / 2 + sizes[idx-1]
        // let value = ((maxN - minN) / 2 + minN) + sizes[idx-1]
        
        sizes.append(value)
    }
    
    // 구간 넓이 구하기
    for range in ranges {
        let a = range[0]
        let b = (paths.count-1) + range[1]
        
        if a > b {
            result.append(-1)
        } else if a == b { 
            result.append(0)
        } else {
            let value = sizes[b] - sizes[a]
            result.append(value)
        }
    }
    
    return result
}

❌ 틀린 이유 및 틀린 부분

문제에서 “이를 [0,0] 구간에 대해 정적분 한다면 전체 구간에 대한 정적분이며” 라고해서
a==0 && b==0 이면 전체 구간에 대해서 넓이를 구했는데

이는 사실 a==0, b==n-0의 형태가 되면서 전체 구간을 구하는 것이었다

그래서 [0, -n] 범위는 [0, 0]이 되어 넓이는 0이 된다.

⏳ 시간 복잡도

O(N) : 각 좌표를 한번 순회하면서 값을 구함

📌 풀이 또는 기억할 정보