[ 프로그래머스 ] 카펫

 

 

🍄 코딩테스트

코딩테스트 문제 풀이

✍🏻 Github

문제 풀이 github 링크

 

 

문제 설명

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.

 

 

Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.

Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
• 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
• 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

 

입출력 예

brown	yellow	return
10	2	[4, 3]
8	1	[3, 3]
24	24	[8, 6]

 

문제 풀이

나의 풀이

import Foundation

func solution(_ brown:Int, _ yellow:Int) -> [Int] {
    
    let n = brown + yellow
    
    for i in 3...Int(sqrt(Double(n))) {
        if n % i == 0 {
            let x = n / i, y = i
            if brown == ( 2 * x + 2 * y - 4 ) {
                return [x, y]
            }
        }
    }
    
    return []
}

 

우선 문제를 풀기 위해서 문제를 이해하는데 시간이 좀 걸렸던 것 같다.

그래서 뭘 구하라고 하는 거지?!

 

예시를 보자마자 약수 구하는 문제라는 것을 직감했다.

노란색 카펫의 값이 항상 1보다 크거나 같다라는 조건이 주어져 있기 때문에 제일 작은 약수의 값은 3일 것이다.

3부터 sqrt(n)까지로 계산을 해 완전탐색으로 풀기로 했다.

( 적으면서 해야 머리가 굴러가는 1인.. )

최댓값인 200,000 + 5,000 의 값은 205,000 이므로 sqrt(205,000) 보다 작은 가장 큰 정수는 452 였기 때문에 450회의 for문이라면 충분히 돌 수 있을 것이라고 생각했다!

 

카펫에 둘러싸인 brown 값은 예시만 몇 개만 계산해봐도 일반화 공식이 나왔다 → ( 2 * x + 2 * y - 4 )

푼 결과 예상대로 정답! 10분정도 걸린 것 같다!

 

 

다른 사람 풀이

import Foundation

func solution(_ brown: Int, _ red: Int) -> [Int] {
    for n in (1...Int(sqrt(Double(red)))).reversed() {
        if (red/n+2) * (n+2) == (brown + red) {
            return [(red/n+2), n+2]
        }
    }
    return [0, 0]
}

왜 굳이 reversed를 한지 의문이다. 출력만 반대로 해도 될텐데!

새로운 공식을 찾아서 푼 것 같아서 신기했다!