[Swift 알고리즘] 프로그래머스(Lv.2) - 멀쩡한 사각형

안녕하세요. 개발 중인 정주입니다.

 

오늘은 프로그래머스(Lv.2) - 멀쩡한 사각형 문제를 풀었습니다.

 

---

목차

---

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

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

코딩테스트 연습 - 멀쩡한 사각형

 

---

풀이

이 문제는 로직 자체를 발견하지 못했습니다..

결국에는 풀이를 볼 수밖에 없었는데요. 

그림을 그려가며 고민할 때 가로선, 세로선과 연관이 있겠구나라는 생각은 했지만...

최대공약수를 이용해 직사각형을 축소하여 로직을 짠다는 건 떠올리지 못했네요 ㅠㅠ

 

자세한 설명은 코드 아래에 적었으니 참고 부탁드리고 마지막에 한 번 더 풀어봐야겠습니다.

 

---

전체 코드

import Foundation

func solution(_ w:Int, _ h:Int) -> Int64{
    let w: Int64 = Int64(w)
    let h: Int64 = Int64(h)
    
    let wholeSquare = w * h
    
    //w * h는 공약수를 나눈 w' * h'로 축소 가능
    //w'와 h'가 서로소일 때 반대쪽 코너로 대각선을 그으면 w'-1개의 세로 선과 h'-1개의 가로 선을 지남
    //깨진 정사각형은 1 + (w'-1) + (h'-1) = w' + h' - 1임
    //공약수를 다시 곱해주면 w + h - gcd(w, h)가 됨
    let broken = w + h - gcd(w, h)
    
    return wholeSquare - broken
}

func gcd(_ a: Int64, _ b: Int64) -> Int64 {
    let maxNum = max(a, b)
    let minNum = min(a, b)
    
    let remain = maxNum % minNum
    return remain == 0 ? minNum : gcd(minNum, remain)
}

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.