[프로그래머스/Swift] 62048번 - 멀쩡한 사각형

🔗 문제 링크

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

💡 구현 아이디어

1. 기울기를 구함
2. 최소 공배수를 구함
3. W * H 사각형을 W/GCD * H(GCD) 사각형으로 압축해서 버리는 사각형의 개수를 구함
4. 전체 W * H에 대해서 사각형 개수를 구하고 버리는 3번에서 구한 사각형의 개수 * 압축 비율로 전체 중에서 사용가능한 사각형의 개수를 구함

💻 코드

import Foundation

func solution(_ w:Int, _ h:Int) -> Int64 {
    
    let width: Int64 = Int64(min(w, h))
    let height: Int64 = Int64(max(w, h))
    
    // let incline: Double = Double(height) / Double(width)
    let gcdNum = gcd(height, width)
    let tempW: Int64 = width / gcdNum
    let tempH: Int64 = height / gcdNum
    
    var result: Int64 = width * height

    for i in 1...tempW {
        let x0 = i-1
        let Dy0 = (Double(height) * Double(x0)) / Double(width)
        let y0 = Int64(Dy0)
        let x1 = i
        let Dy1 = (Double(height) * Double(x1)) / Double(width) 
        var y1 = Int64(Dy1)
        if Dy1 - Double(y1) > 0 {
            y1 += 1
        }
        result -= (y1-y0) * gcdNum
    }
    
    
    return result
}

func gcd(_ a: Int64, _ b: Int64) -> Int64 {
    if a % b == 0 { return b }
    return gcd(b, a % b)
}

❌ 틀린 이유 및 틀린 부분

기존에 let incline: Double = Double(height) / Double(width) 를 구하고 let Dy0 = incline * Double(x0) 를 해줬더니 부동소수점 오류로 인해서 계속 틀렸다…

⏳ 시간 복잡도

O(N) : 가로 길이만큼 접근

📌 풀이 또는 기억할 정보