[알고리즘] 카펫

출처: 프로그래머스 코딩 테스트 연습

문제 요약

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를 모두 합한 값이 카펫의 면적이 된다. 따라서 카펫의 면적을 만들 수 있는 경우의 수를 파악해야 한다. 첫 번째 예를 보면 brown과 yellow를 모두 합한 값은 12가되고 12를 만들 수 있는 경우의 수는 [1, 12], [2, 6], [3, 4], [4, 3], [6, 2], [12, 1] 이 된다.
이때 가로의 길이가 세로의 길이보다 같거나 커야 함으로 다시 한번 더 필터를 거쳐 가로의 길이가 더 긴 경우의 수만 남긴다.
따라서 [4,3], [6,2], [12, 1]을 얻을 수 있다. 한 가지 더 필터를 추가하면 세로의 길이가 1또는 2일 경우에는 brown 격자로 감쌀 수 없다. 따라서 세로의 길이는 반드시 3보다 같거나 커야 한다.

const allColor = brown + yellow;
const sumArr = [];
const possibleCase = [];
let answer;
for(let i = 1; i <= allColor; i++) {
  if(allColor % i === 0) sumArr.push([i, allColor / i]);
}
sumArr.forEach((sum) => {
  if(sum[0] >= sum[1]) {
    if(sum[1] > 2) possibleCase.push(sum)
  }
});

여기서는 결과값이 [4,3]하나가 되기 때문에 곧바로 리턴하면 되지만 한 가지 더 확인해야할 부분이 있다.
문제에서 테두리 1줄은 brown으로 칠해져 있다고 했기 때문에 전체 면적에서 테두리 면적을 뺀 부분이 yellow와 같아야 정답이 된다.
따라서 조건을 추가한다.

possibleCase.forEach((c) => {
  const w = c[0];
  const h = c[1];
  const yellowArea = w * h - ((w + h) * 2 - 4)
  
  if(yellow === yellowArea) {
    answer = c;
  }
});
return answer;

이때 둘레에서는 사각형의 꼭짓점에 해당하는 4개의 중복되는 부분을 제거해줘야 한다. 선이 아니라 면이기 때문에 4를 빼지 않으면 정확한 둘레를 얻을 수 없다. 만약 yellow와 yellowArea가 일치하면 정답이 되는 케이스이기 때문에 반환한다.

전체 코드

function solution(brown, yellow) {
    const allColor = brown + yellow;
    const sumArr = [];
    const possibleCase = [];
    let answer;
    for(let i = 1; i <= allColor; i++) {
        if(allColor % i === 0) sumArr.push([i, allColor / i]);
    }
    sumArr.forEach((sum) => {
        if(sum[0] >= sum[1]) {
            if(sum[1] > 2) possibleCase.push(sum)
        }
    }) 
    possibleCase.forEach((c) => {
        const w = c[0];
        const h = c[1];
        const yellowArea = w * h - ((w + h) * 2 - 4)
        
        if(yellow === yellowArea) {
            answer = c;
        }
    })
    return answer;

}

마무리

안풀리는 문제들이 많아서 너무 힘든 나날들을 보내고 있었는데 오랜만에 재밌는 문제를 만난것 같다. 다른 사람들의 풀이 방법을 보고 아직 많이 부족하다는 생각이 들었지만 그래도 조금씩 혼자서 문제를 푸는 능력이 늘어나고 있어서 너무 좋았다.