[JavaScript] 프로그래머스 코딩테스트 레벨 2 : 카펫

📌  문제

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]

---

📌  풀이

알아야 하는 것

• 카펫의 가로 길이는 세로 길이와 같거나 세로 길이보다 길다.
• yellow의 약수 구하는 방법 
  • yellow = 12라면 for문으로 i = 1, i <= yellow; i++ 처럼 순회해서 구할 수도 있다. [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
  • 하지만 for문으로 i = 1, i * i <= yellow; i++ 처럼 i를 1부터 yellow의 제곱근까지 증가 시키면서 약수를 찾으면 불필요한 반복횟수를 줄일 수 있다. 제곱근인 3까지만 확인하면 12의 모든 약수를 구할 수 있기 때문.

구할 것

• [yellow / yellow의 약수, yellow의 약수] 중 1번째 원소가 2번째 원소보다 크거나 같은 경우 (가로 >= 세로)

예컨대 brown = 24, yellow = 24일 때 yellow의 약수는 [1, 2, 3, 4, 6, 8, 12, 24]가 나온다.

yellow를 구성할 수 있는 약수의 쌍을 만들면 [1, 24] [2, 12]... [24, 1] 이런 식으로 쌍이 만들어진다.

이 때 1번째 원소가 가로가 될 것이니 yellow / yellow의 약수 가 i보다 큰 경우만 담는다.

 

그런 경우를 ans에 담아 보면 [[24, 1], [12, 2], [8, 3], [6, 4]]가 된다.

brown = (1번째 원소*2) + (2번째 원소*2) +4 이기에 해당 조건을 부합하는 2차원 배열에는 2씩 더해준다.

function solution(brown, yellow) {
  let ans = [];

  for (let i = 1; i * i <= yellow; i++) {
    if (yellow % i === 0) {
      if (yellow / i >= i) {
        ans.push([yellow / i, i]);
      }
    }
  }

  for (let i = 0; i < ans.length; i++) {
    if (ans[i][0] * 2 + ans[i][1] * 2 === brown - 4) {
      return [ans[i][0] + 2, ans[i][1] + 2];
    }
  }
}

 

항상 풀고 나면 생각보다 간단한데? 싶지만 이전에 풀었던 코드를 보면 좀 가관이다.

처음에 조건을 짤 때 약수를 잘못 구해서 yellow가 1일 경우를 또 고려한 조건을 만들었고, 약수를 구하는 데만 반복문을 2번 사용했다. 전체적으로 망한 코드1은 O(yellow)로, 최종 코드는 O(√yellow)가 나왔다. 시간복잡도도 줄어들었고 코드도 훨씬 깔끔해졌다.

function solution(brown, yellow) {
  let ans = [];

  for (let i = 1; i <= yellow; i++) {
    if (i / yellow === 0) {
      ans.push([1, 1]);
    } else if (parseInt(yellow / i) * i === yellow) {
      ans.push([yellow / i, i]);
    }
  }

  let ans2 = [];

  for (let i = 0; i < ans.length; i++) {
    if (ans[i][0] >= ans[i][1]) {
      ans2.push([ans[i][0], ans[i][1]]);
    }
  }

  let ans3 = [];

  for (let i = 0; i < ans2.length; i++) {
    if (ans2[i][0] * 2 + ans2[i][1] * 2 + 4 === brown) {
      ans3.push(ans2[i][0], ans2[i][1]);
    }
  }
  return ans3.map((v) => v + 2);
}

 

그래도 장족의 발전을 했다는 생각이 드는 게 아마 두 달 전에 이 문제를 풀었을 땐 요상한 코드로 실패했었다.

철저히 테스트 케이스만 고려해서 풀어버린... ㅋㅋ 와 많이 컸다!  

function solution(brown, yellow) {
let yellowROW = [];

for (let i = 1; i <= yellow; i++) {
if (yellow % i === 0) {
yellowROW.push(i);
}
}
if (yellowROW.length === 0) {
yellowROW.push(yellow);
}

let RW = yellowROW.filter((item) => item < 8);

/*가로 세로 */
let realROW = Math.max(...RW);
let realCOL = yellow / realROW;

let brwROW = realROW + 2;
let brwCOL = realCOL + 2;

return [brwROW, brwCOL];
}