[Lv2] 카펫

프로그래머스

• https://programmers.co.kr/learn/courses/30/lessons/42842

나의 풀이

수도코드

• 가로와 세로의 길이는 최소 3이상이다.
  • 가로와 세로가 1 또는 2인 경우, 중앙이 생길 수 없다. 최소 3*3 이상부터 중앙에 노란격자가 생길 수 있다.
• 가로는 세로보다 크거나 같다.
• 노란격자의 크기는 (가로-2)*(세로-2)이다.
• 노란격자 + 갈색격자 = 전체 격자의 개수이므로, 전체 격자의 약수를 구한다.
• 약수들은 하나는 가로길이, 하나는 세로길이로 짝지어진다.
• 가로의 길이와 세로의 길이가 같다면 (정사각형) [가로, 세로]를 리턴한다.
• (가로-2)*(세로-2)가 노란격자 크기인 경우, [가로,세로]를 리턴한다.

function solution(brown, yellow){
  function getDividers(num) {
    const dividers = [];
    for(let i=3; i<=Math.sqrt(num); i++){
      if(num%i===0){
        dividers.push(i);
        if(num/i===i)continue
        dividers.push(num/i);
      }
    }
    return dividers;
  }
  const dividers = getDividers(brown+yellow);
  while(dividers.length){
    const vertical = dividers.shift();
    const horizontal = dividers.shift() === undefined ? vertical : (brown+yellow)/vertical;
    if(vertical === horizontal){
      return [horizontal, vertical];
    }
    else if((vertical-2)*(horizontal-2)===yellow){
      return [horizontal, vertical];
    }
  }
}

다른 분의 풀이

• 세로(i)는 3이상 전체 격자수/i이하이다.
• 가로(x)는 전체격자수/i이다.
• 이때, x와 y는 모두 자연수이다.
• (x-2)*(i-2) === yellow인 경우, [x,i]를 리턴한다.

function solution(brown, yellow){
  var answer = [];
  for(var i=3; i <= (brown+yellow)/i; i++){
    var x = Math.floor((brown+yellow)/i);
    if((x-2)*(i-2) === yellow) return [x,i];
  }
}

나의 풀이는 전체격자수의 약수를 배열에 저장했다. 그리고 그 배열의 요소를 2개씩 빼면서 각각의 값에서 2를 뺀 것들의 곱이 노란격자수와 일치하는지 확인했다. 그래서, 실행시간이 4초~15초까지 걸렸다.

그런데 다른분의 풀이를 보니, 굳이 약수를 구할 필요가 없었다. i가 세로의 길이가 될 수 있는 범위이고 가로길이 x는 전체 범위에서 i를 나눈 값이다. 따라서 각 i와 x에 대해 2를 뺀 것들의 곱이 노란격자수와 일치하는지 확인해주면 된다. 이 풀이법은 실행시간이 0.2초 미만으로 걸렸다.

약수를 직접 구하지 않고, 약수의 개념만으로도 풀 수 있는 문제였다.