[Swift] 프로그래머스 멀쩡한 사각형 풀이

Programmers 스위프트 멀쩡한 사각형 풀이

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

 

 

 

문제인 즉 위 그림에서 회색 사각형의 개수를 구하라는 건데 .... 

처음에는 이게 최대공약수 문제인지 감도 잡지 못했다.

그러나 12 * 8 = 96이고, 이중에서 4의 제곱인 16이 뭔가 최대공약수를 이용하는건가 싶어 시도해봤더니 역시나 그랬다.

내 풀이는 이렇다. 먼저 최대공약수를 구한다. 그리고 최대공약수로 나눈 width와 최대공약수로 나눈 height도 구한다. 

이들 셋은 각각 반복되는 사각형의 개수, 반복되는 사각형의 Width, 반복되는 사각형의 Height가 된다.

 

반복되는 사각형에서는 반복되는 사각형의 크기에서 width + height를 빼주면 회색 사각형의 개수를 구할 수 있다.

그런데 반복되는 사각형의 크기에서 width는 가로, height는 세로 대각선에 걸리는 녀석의 개수를 센 건데 

사실 첫 번째, 그러니까 왼쪽 상단 사각형은 겹치는 요소라고 볼 수 있으므로 1을 빼준다.

 

내코드는 다음과 같다:

import Foundation

func GCD(_ num1: Int64, _ num2: Int64) -> Int64 {
    let remain = num1 % num2 
    if remain == 0 {
        return num2
    } else {
        return GCD(num2, remain)
    }
}


func solution(_ w:Int, _ h:Int) -> Int64{
    var width = Int64(min(w, h))
    var height = Int64(max(w, h))
    
    let sum = width * height
    let gcd = GCD(height, width)
    
    
    return sum - (width / gcd + height / gcd - 1) * gcd
}

 

 

다른사람의 모범 답안도 공개한다. 

(출처: https://hongdonghyun.github.io/2020/06/Swift-%EB%A9%80%EC%A9%A1%ED%95%9C-%EC%82%AC%EA%B0%81%ED%98%95/)

func GCD (_ a:Int64, _ b: Int64) -> Int64 {
    let remain = a % b
    if remain == 0 {
        return b
    } else {
        return GCD(b, remain)
    }
}

func solution(_ w:Int, _ h:Int) -> Int64{
    let w64 = Int64(w), h64 = Int64(h)
    return (w64 * h64) - (w64 + h64 - GCD(w64, h64))
}