[프로그래머스] 카펫 (Swift)

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

코딩테스트 연습 - 카펫

완전 탐색

 

카펫 문양의 규칙은 테두리 한줄은 brown으로 칠하고, 그 안쪽은 모두 yellow로 칠하는 것이다.

brown으로 칠해진 칸의 개수와 yellow로 칠해진 칸의 개수가 주어지면

카펫의 가로와 세로 길이를 담아 반환하는 문제

 

접근방법

처음에는 brown 개수와 yellow 개수를 합한 것이 카펫의 넓이니까

해당 넓이를 만족하는 가로,세로 쌍을 구하고 그 조건에서 brown 개수, yellow 개수를 구해서 주어진 값과 같으면 가로,세로를 반환하는 식으로 구현했다.

 

근데 풀이 후에 다른분들 코드를 보고 합을 구할 필요 없이 안쪽사각형 넓이만으로 답을 구할 수 있어서 다시 풀이했다.

 

yellow개수 = 안쪽 사각형 넓이. 이 넓이를 만족하는 가로,세로를 구하고(세로길이에 1부터 넓이의 제곱근까지 대입해가면서)

안쪽 사각형 가로,세로 길이에 따른 brown 개수 = 안쪽가로*2 + 안쪽세로*2 + 4(꼭짓점)

이 brown 개수가 주어진 brown 값과 일치하면 이때의 가로,세로를 배열에 담아 반환한다.

 

 

소스코드

import Foundation

func solution(_ brown:Int, _ yellow:Int) -> [Int] {

    for yellowHeight in 1...Int(sqrt(Double(yellow))) {
        if yellow % yellowHeight == 0 {
            let yellowWidth = yellow/yellowHeight
            
            let numOfBrown = yellowHeight*2 + yellowWidth*2 + 4
            
            if brown == numOfBrown {
                return [yellowWidth+2, yellowHeight+2]
            }
        }
    }
    return []
}

개선 풀이

import Foundation

func solution(_ brown:Int, _ yellow:Int) -> [Int] {
    let sum:Int = brown + yellow

    for d in 3...Int(sqrt(Double(sum))) {
        if sum % d == 0 {
            let r = d
            let c = sum/d
            
            let cbrown = 2*(r+c-2)
            let cyellow = (r-2)*(c-2)
            
            if brown == cbrown && yellow == cyellow {
                return [c,r]
            }
        }
    }
    return []
}

최초 풀이