프로그래머스 - 카펫 (Javascript)

코로나에 걸려버렸다..
뭐 아직까진 무증상에 가깝지만 집에 가만히 있기 따분해서 격리 기간동안 알고리즘이나 열심히 풀어보려 한다..!!

문제 설명

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]

---

소스코드 (첫 시도)

프로그래머스에서는 틀린 테스트케이스를 확인할 수가 없어서…
도저히 아래 풀이법이 왜 틀린건지 모르겠다 ㅜ 아래와 같이 풀면 시간복잡도도 굉장히 우수할 것 같은데 말이다.

function solution(brown, yellow) {
  const answer = [];
  let border = 0;
  function paint(row, col) {
    if (!col) return;
    border = 2 * (row + col) + 4;
    if (border === brown) {
      return answer.push([col + 2, row + 2]);
    }
    paint(row * 2, col / 2);
    return;
  }
  paint(1, yellow);
  return answer[0];
}

소스코드 (최종)

그냥 욕심을 버리고 순차적인 탐색법을 통해 풀었더니 모든 테스트케이스를 통과할 수 있었다.
그리고 추가적으로, 반복문 조건에서 Math.sqrt()를 사용하며 시간복잡도를 대폭 개선할 수 있었다.

function solution(brown, yellow) {
  const answer = [];
  const size = brown + yellow;
  let col;
  for (let row = 3; row <= Math.sqrt(size); row++) {
    if (size % row !== 0) continue;
    col = size / row;
    if ((col + row) * 2 - 4 === brown) answer.push(col, row);
  }
  return answer;
}

반복문 조건 시작점이 3인 이유

Yellow는 반드시 한 줄이 필요하다. 따라서 Yellow가 한 줄일 때 위 아래로 한 줄씩 brown이 감싸면 총 row는 3이 되기 때문에 반복문의 시작점이 3인 것이다.

조건문에서 Math.sqrt()를 사용한 이유

문제의 제한사항 때문이다!
문제에서는 반드시 카페트가 정사각형 또는 가로가 더 긴 직사각형이어야 한다고 했다.

위 그림을 기준으로 설명을 해보면, 반복문의 종료지점은 size 30의 제곱근인 5.xx가 될 것이다.

이는 쉽게 말해 row의 최대값이 5라는 것이다. 왤까? 아래의 그림을 살펴보자.

위 그림에서 자세히 나와있듯, 이번 문제의 제한사항에서 row가 가질 수 있는 최대값은 딱 size의 제곱근 까지다. 이 덕분에 반복문의 반복횟수를 효과적으로 감축할 수 있었다.

---