[프로그래머스] 완전탐색 _ 카펫 (javascript)

2021_10_10 알고리즘 스터디 문제 풀이

문제 URL 

코딩테스트 연습 - 카펫

문제

문제를 보고 가장 중요한 부분을 먼저 확인했다.

x >= y의 조건을 성립하고, brown은 직사각형이 테두리 한 줄을 차지하며 yellow는 brown을 제외한 공간을 차지한다.

어차피 x의 길이는 y와 같거나 길어야한다는 조건이 있기때문에 제곱근을 먼저 구해 초기 x값을 디폴트로 지정하는 방법을 생각했다.

 

수도코드

상수 blocks 선언, brown + yellow 값, 전체 블록의 개수를 저장한다/
변수 x 선언, blocks의 제곱근을 구하고 Math.ceil을 통해 가장 근접한 정수를 구한다(y가 x보다 클 수 없기때문)

while문을 통해 x가 blocks의 값이 될때까지 순회
	변수 y선언, blocks / x를 할당한다
    
	Number.isInteger 메소드를 통해 y가 정수이고, yellow가 (x - 2) * (y - 2)인 경우
    	[x, y] 를 리턴한다
    그렇지 않을 경우
  	x의 값을 1씩 증가시킨다

y의 값이 정수가 나오지 않는다면, 카펫을 잘라서 사용할 순 없기때문에 x의 값을 1씩 증가시킨다.

또한 yellow의 패턴이 일치하는 지 확인 하기 위해 (x - 2) * (y - 2)로 추가 조건을 설정하고 정답을 찾아낸다

코드

function solution(brown, yellow) {
    const blocks = brown + yellow;
    let x = Math.ceil(Math.sqrt(blocks));
    
    while (x <= blocks) {
        const y = blocks / x;
        
        if (Number.isInteger(y) && yellow === (x - 2) * (y - 2)) {
            return [x, y]
        }
        x++;
    }
}

시간 복잡도 O(n)의 코드를 구현했다.