프로그래머스 - 카펫 level 2

문제

• 갈색으로 테두리가 1줄 둘러져있고 중앙에는 노란색이 칠해져 있는 카펫이 있다.
• 갈색 격자의 수와 노란색 격자의 수가 주어질 때, 카펫의 가로 세로 규격을 반환하라.

 

문제풀이

1. 주어진 노란색 격자로 만들 수 있는 모든 [가로, 세로]를 순회한다.

2. 그렇게 사각형 중 둘레의 길이가 갈색 격자의 수와 같은 것이 있으면 정답을 찾은 것.

3. 노란색 사각형의 가로 세로를 반환하는게 아니라, 거기에 갈색 격자까지 합했을때의 가로 세로 크기를 반환해야하므로 노란 사간형의 가로 세로 길이에 2씩 더해준다.

function solution(brown, yellow) {
    let y = 0
    while (++y) {
        const x = yellow / y
        if (y > x) {
            break
        }
        const perimeter = 4 + y*2 + x*2
        if (x%1 === 0 && perimeter === brown) {
            return [x + 2 , y + 2]
        }
    }
}

시간복잡도: yellow를 n으로 잡고 계산하면 O(n). yellow가 2000000 이하로 제한되어있으므로 O(1). 

공간복잡도: O(1)