[프로그래머스] Lv.02 카펫 (JavaScript)

문제

프로그래머스

 

문제 설명

위 사진과 같은 카펫이 있다고 합니다. 카펫에서 갈색 적자의 수를 담은 변수 brown, 노란색 격자의 수를 담은 변수 yellow가 매게변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 반환하면 되는 문제 입니다.

 

※제한 사항

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

풀이

중앙은 모두 노란색 격자로 채워지는 카펫이므로 카펫의 넓이는 (노란색 격자 가로+2) * (노란색 격자 세로+2)가 되는 규칙이 있습니다. 그래서 처음 접근했던 방법은 아래 코드처럼 이중 반복문을 돌려 모든 경우의 수를 구한 다음 그 중 (노란색 격자 가로+2) * (노란색 격자 세로+2)에 해당하는 부분을 반환해주는 방식으로 구현하였는데, 이 방법으로 구현하니 시간 초과 문제가 있었습니다.

function solution(brown, yellow) {
    var answer = [];
    
    for(let height=1; height<=yellow; height++){
        for(let width=1; width<=yellow; width++){
            if(height*j === yellow && width>=height){
               if((width+2)*(height+2) === brown+yellow){
                    return width+2, height+2
                } 
            }
        }
    }
    
}

 

그래서 시도한 방법은 재귀를 통한 반복이였습니다. 아래 코드와 같이 재귀로 바꿔주니 속도는 해결이 됐지만 런타임 오류가 발생했습니다.

function solution(brown, yellow) {
    var answer = [];
    
    const operator = (width) => {
        if(width === yellow+1){
            return;
        }
        
        operator(width+1)
        
        for(let j=1; j<=yellow; j++){
            if(width*j === yellow && j >=width){
                if((j+2)*(width+2) === brown+yellow){
                    answer.push(j+2, width+2)
                } 
            }
        }
    }
    
    operator(1)
    
    return answer;
}

 

그래서 고민하다 생각한 방법은 첫 번째 방법을 유지하되 반복을 줄이는 식으로 구현하였습니다. 첫 번째 코드랑 돌아가는 방식은 똑같지만 쓸모없는 반복을 줄여 최대한 빠른 탐색을 하는 방식으로 바꿨습니다.

아래는 풀이에 사용한 코드입니다.

function solution(brown, yellow) {
    var answer = [];
    // 넓이를 저장한 변수
    let width = brown + yellow
    // yellow만큼 반복문을 실행시킵니다.
    // width = (yellow가로+2) * (yellow세로+2) 임을 이용하여
    // height를 구해 최소한의 반복으로 width와 height를 구해주었습니다.
    // i * (height-2) === yellow일 시 조건에 해당하는 가로 세로 길이이므로 
    // 해당 값을 반환해주었습니다.
    for(let i=yellow; i>0; i--){
        const height = width / (i+2)
        if((height-2) * i === yellow) {
            if(height-2 >= i) {
                return [height, i+2]
            }
        }
    }
    
}