[알고리즘] 프로그래머스 카펫

문제 설명

문제의 입출력 예는 다음과 같다.

brown	yellow	return
10	2	[4,3]
8	1	[3,3]
24	24	[8,6]

🔎 문제 링크

문제 풀이

이 문제를 보고 일단 answer라는 빈 배열을 선언하고, 전체 격자의 갯수를 구했다. brown+ yellow만 하면 되서 간단했다.

let answer = [];
const total_grid = brown + yellow;

전체 격자의 갯수를 알고 있기 때문에, total_grid의 약수를 구하면 width와 height 값을 구할 수 있을 것 같다는 생각이 들었다. 가로 x 세로 = 총 갯수 니까. 그래서 total_grid의 약수를 구해서 answer 배열에 넣어주는 for문을 돌렸다.

  for (let i = 2; i < total_grid; i++) {
    if (total_grid % i === 0) {
      answer.push(i);
    }
  }

이 패턴이 성립하기 위해선 가로나 세로값이 3 이상이어야 하니까 i=3으로 했더니 문제가 생겼다. 어떤 문제였는지는 아래에서 설명하겠다.

테스트케이스 3번(brown이 24, yellow가 24)을 예시로 들면 48의 약수들이 담긴 answer 배열은 다음과 같다.

[2,3,4,6,8,12,16, 24]

2 x 24는 48이다.
3 x 16은 48이다.
4 x 12는 48이다.
.
.
.
이런 식으로 배열의 첫번째 값과 마지막 값을 곱하면 전체 격자의 갯수가 된다. 그래서 나는 저 숫자들이 각각 height과 width가 될 수 있다고 생각했다. (그렇기 때문에 i=3으로 하면 24가 짝이 없기 때문에 3과 24, 4와 16처럼 잘못된 페어끼리 묶이게 되는 위험이 있다.)

그럼 저 숫자들 중에 어느 페어가 내가 찾는 가로와 세로값인지 어떻게 알 수 있을까? 격자를 그려서 곰곰히 생각해보다가 다음과 같은 공식을 떠올렸다.

테두리 1줄이 brown이니까, (width-2) * (height-2)를 하면 yellow가 된다.

그래서 while문으로 배열의 맨앞과 맨끝을 비교해서 그 숫자에 각각 2를 빼서 곱한 값이 yellow가 되면 그 값을 return하고, 아니면 배열에서 slice 하는 코드를 썼다.

예를 들자면

2-2 = 0 , 24-2 = 22, 0 x 22 = 0

결과값과 yellow가 같지 않으니까 배열에서 제거하고, 이제 3과 16이 각각 answer의 첫번째 값과 마지막 값이 된다. 이런 식으로 없애나가다가 마지막 두 수가 남으면(answer의 length가 2가 되면) answer로 리턴하는 코드를 썼다. 처음에 이렇게 해결하고 다 됐다고 생각했는데, 허점이 있었다. width와 height의 차이가 클 경우, 꼭 마지막 두 수가 정답이 된다는 보장이 없다는 것이다. 그래서 기존의 length가 2가 되면 answer를 return하는 코드 대신 [width, height]을 return 해주는 것으로 코드를 수정했다.

전체 코드는 다음과 같다.

function solution(brown, yellow) {
  var answer = [];
  const total_grid = brown + yellow;

  for (let i = 2; i < total_grid; i++) {
    if (total_grid % i === 0) {
      answer.push(i);
    }
  }
  if (answer.length === 1) {
    return answer.concat(answer);
  }

  while (answer.length !== 2) {
    const height = answer[0];
    const width = answer[answer.length - 1];
    if ((width - 2) * (height- 2) === yellow) {
      return [width, height] 
    } else {
      answer = answer.slice(1, answer.length - 1)
    }
  }
  return answer.reverse()
}

(참고로 마지막에 reverse를 해준 이유는 width값이 height보다 크기 때문이다.)