[프로그래머스] 멀쩡한 사각형 - 최대공약수 구하기

 

▼ 문제 링크

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

 

풀이 1, 2 할 거 없이 처음부터 테스트 케이스를 전부 다 만족하지 못해서 결국 눈물을 꾹 참으면서 어린 시절 구몬 학습지 맨 뒷장 펼쳐서 답안지 베끼던 실력으로 구글링했다.

그치만 뭐... 다 이러면서 크는 거지 

출처: https://leedakyeong.tistory.com/entry/프로그래머스-멀쩡한-사각형-in-python [슈퍼짱짱]

 

 

# 풀이
최대공약수와 유클리드 호제법

import Foundation

func solution(_ w: Int, _ h: Int) -> Int64 {
    let answer: Int64 = Int64(w * h)
    let gcd = getGcd(w, h)
    
    return answer - Int64(w + h - gcd)
}

// 최대공약수 구하기 - 유클리드 호제법
func getGcd(_ num1: Int, _ num2: Int) -> Int {
    guard num1 != 0 && num2 != 0 else {
        return 0
    }
    
    guard num1 != 1 && num2 != 1 else {
        return 1
    }
    
    guard num1 % num2 != 0 else {
        return num2
    }
    
    guard num2 % num1 != 0 else {
        return num1
    }
    
    var big = (num1 > num2 ? num1 : num2)
    var small = (num1 < num2 ? num1 : num2)
    
    while big % small != 0 {
        let temp = big % small
        big = small
        small = temp
    }
    
    return small
}

처음에는 최대공약수랑 무슨 상관이지 싶었는데, 자세히 보니 특정한 패턴이 최대공약수만큼 반복하고 있었다.

문제에 주어진 예시

문제에 주어진 예시인 (8x12)를 살펴봐도 기울기 그래프를 따라 (2x3)칸이 4번 반복되는 것을 확인할 수 있다.

대각선을 가로지르는 선과 연관된 사각형 반복 패턴
(가로 / 최대공약수) x (세로 / 최대공약수) * 최대공약수

 

확대한 패턴의 일부

반복되는 패턴을 떼어 일부만 확대해보면 위와 같다. 이때, 대각선에 직접적으로 영향을 받는 정사각형의 개수는 (패턴의 가로 + 패턴의 세로 - 1) 이다. (이때 가로, 세로는 종이 전체가 아니라 확대하여 잘라낸 패턴의 가로, 세로)
이런 패턴이 최대공약수 만큼 반복되므로, 결과적으로 (가로 + 세로 - 최대공약수)가 된다. (이때 가로, 세로는 전체 종이의 가로, 세로)

 

 

# 최대공약수 구하는 법
유클리드 호제법에 대하여… 

위키피디아에서 설명하는 유클리드 호제법은 다음과 같다.

2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

➡️ 큰 수를 작은 수로 나눈 나머지값으로 다시 작은 수를 나누는 과정을 나머지가 0이 될 때까지 반복한다. 마지막(나머지가 0이 될 때)에 사용된 "작은 수"가 두 수의 최대공약수이다.

유클리드 호제법으로 48과 18의 최대공약수를 구하는 과정을 살펴보면 다음과 같다.

48 % 18 = 12
18 % 12 = 6
12 % 6 = 0
➡️ 마지막 계산식의 6이 48과 18의 최대공약수가 됨

 

코드로 나타내면 다음과 같다.

while big % small != 0 {
  let temp = big % small
  big = small
  small = temp
}

위 반복문 과정을 통해 가장 마지막 small값이 최대공약수가 된다.