프로그래머스 문제이다.
카펫의 크기를 구하는 문제인데
예시로 나온 답안을 살펴보니 다음과 같았다.
return값을 살펴보니 brown과 yellow의 합에서 약수를 구해서 가장 중앙값을 반환하면 답이 될 것 같았다.
function solution(brown, yellow) {
let a = brown + yellow
let arr = []
let count = 0;
for(let i = 0; i <= a; i++){
if(a%i == 0){
arr[count] = a/i
count++
}
}
let l = arr.length/2
for(let j = 0; j < l; j++){
if(arr.length > 2){
arr.shift()
arr.pop()
}else{
return arr.length === 2 ? arr : [arr[0], arr[0]]
}
}
}brown과 yellow의 합의 약수가 들어간 배열을 생성하고
가장 중앙에 가까운 값을 찾아야 하므로 shift와 pop을 통해서 한칸씩 제거해주어
중앙에 존재하는 값을 찾아서 반환했다.
만약 배열의 길이가 홀수여서 1칸이 남게 될 경우 해당 요소를 두번 담은 배열을 반환했다.
이 경우 문제들이 풀리긴 했지만 반례가 존재했다.
18, 6과 같은 경우
갈색이 노란색을 둘러쌀 수 없기에 [6,4]는 성립하지 않으며 답은 [8, 3]이 된다.
조금 차분하게 다시 생각해보았는데
노란색으로 이루어진 사각형에서 인접한 사각형의 개수 + 4가 갈색 사각형의 개수임을 확인했다.
function solution(brown, yellow) {
let a = yellow
let arr = []
let count = 0;
for(let i = 0; i <= a; i++){
if(a%i == 0){
arr[count] = a/i
count++
}
}
let l = arr.length/2
for(let j = 0; j < l; j++){
if(arr.length > 1){
let w = arr.shift()
let h = arr.pop()
if(brown-4 == w*2+h*2){
return [w+2,h+2]
}
}else{
let w = arr.shift()
let h = w
if(brown-4 == w*2+h*2){
return [w+2,h+2]
}
}
}
}아까랑 같은 방식으로 이번에는 노란색으로만 이루어진 사각형의 약수가 담긴 배열을 생성했다.
(이는 노란색으로 이루어진 사각형의 종류와 같다.)
여기서 가로와 세로로 짝지어져 있으니 길이를 절반으로 잡았고
배열의 첫 번째 값과 마지막 값을 각각 가로와 세로로 두어
아까 말했던 조건을 충족할 경우 return되도록 구성했다.
배열의 길이가 1인경우 예외처리도 잊지 않았다.
이렇게 하여 답을 찾긴 했으나 for문이 두 번 돌아가며 시간이 오래 걸렸다.
이전 풀이방법에 집착하여 배열을 생성했으나
굳이 배열을 생성해서 shift와 pop으로 추출해낼 이유가 있을까 싶어 나누는 동시에 비교하는 로직으로 바꿔보았다.
function solution(brown, yellow) {
let a = yellow
let count = 0;
for(let i = 0; i <= a; i++){
if(a%i == 0){
let w = a/i
let h = i
if(brown-4 == w*2+h*2){
return [w+2,h+2]
}
}
}
}작동도 문제 없이 실행되었으며, 예외처리를 따로 해줄 필요도 없어졌고,
기존 10.97ms 걸리던 문제가 0.18ms로 큰 폭으로 줄어들었다!
