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

 

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

가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을

programmers.co.kr

 

 

 

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

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

그러나 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))
}

 

  • 네이버 블러그 공유하기
  • 네이버 밴드에 공유하기
  • 페이스북 공유하기
  • 카카오스토리 공유하기
// custom