문제 설명
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]풀이 및 분석
brown 과 yellow 를 더하면 전체 타일의 갯수와 같다.
가로와 세로를 곱하면 전체 넓이와 같으므로, 가로&세로는 전체 타일의 약수 중에 있을 수밖에 없다.
ex. 10, 2, [4,3]
전체 타일 갯수 : 10 + 2 = 12개
12의 약수 : 1,2,3,4,6,12
12의 약수 중 가운데 2개 -> [4,3]
- 약수의 대칭성을 이용해 루트값까지만 구했고, 가운데 값을 빨리 찾기 위해 시작을 2부터 하지 않고 거꾸로 했다.
- answer의 0번째에 가로, 1번째에 세로가 와야 하고, 조건에서 가로 길이가 세로 길이보다 길다고 했으므로
n/i를 먼저 넣고,i를 넣는다.
가운데 2개만 무조건 고르면 된다고 생각해서 이렇게 풀었는데, case 4,6,7에서 틀렸다.
function solution(brown, yellow) {
var answer = [];
let n = brown + yellow;
for(let i=Math.floor(Math.sqrt(n));i>=2;i--){
if(n % i === 0){
answer.push(n / i);
answer.push(i);
break;
}
}
return answer;
}⭐️ 반례
test case 4,6,7을 통과하려면 (x-2)(y-2)==yellow를 검증해야 한다.
예시)
(18,6) 이 주어진 값일 때, solution=[8,3]이 나와야한다.B B B B B B B B B Y Y Y Y Y Y B B B B B B B B B위의 방식처럼 무조건 가운데 2개만 고르면 [6,4] 가 나오기 때문에, 추가적인 검증을 해주어야 한다.
보완
- 가독성을 위해 가로와 세로 길이를 각각
width,height이라는 변수에 저장했다. (width-2) * (height-2) === yellow로 검증을 추가해주었다.
function solution(brown, yellow) {
let answer = [];
let total = brown + yellow;
for(let i = Math.floor(Math.sqrt(total));i >= 2;i--){
let width = total/i;
let height = i;
if(total % i === 0 && (width-2) * (height-2) === yellow){
answer.push(width);
answer.push(height);
break;
}
}
return answer;
}다른 풀이
i를 높이로, x를 가로로 설정하고 풀었다.
(최소 높이가 3이므로 i=3으로 설정, 범위는 가로 길이보다 같거나 작게)
메모리 사용량이 조금 더 많고, 시간도 조금 더 오래 걸린다.
function solution(brown, red) {
var answer = [];
for (var i = 3; i <= (brown+red)/i; i++) {
var x = Math.floor((brown+red)/i);
if( (x-2)*(i-2)=== red) {
break;
}
}
return [x,i];
}