리액트 심화 프로젝트 (4)

신나는 알고리즘 풀이 시간. 

문제 이해

Leo는 아래 그림처럼 노란색과 갈색 격자로 구성된 카펫을 보고 가로와 세로의 크기를 유추하려 합니다.

• 갈색 격자(brown): 테두리를 이루는 격자의 개수
• 노란색 격자(yellow): 중앙에 위치한 격자의 개수

예를 들어, 갈색 격자가 10개, 노란색 격자가 2개일 때, 카펫의 가로와 세로는 각각 4와 3입니다.

제한사항

1. 갈색 격자 개수는 8 이상 5000 이하의 자연수
2. 노란색 격자 개수는 1 이상 2,000,000 이하의 자연수
3. 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

문제 풀이 과정

문제를 해결하기 위해 아래의 순서로 접근했다.

1. 총 격자 수 계산

카펫의 전체 격자 수는 갈색과 노란색 격자의 합이었다.

const total = brown + yellow;

2. 가능한 가로와 세로 조합 찾기

전체 격자 수의 약수를 이용해 가로(width)와 세로(height)의 조합을 구했다. 이때 가로는 세로보다 크거나 같아야 하므로, 약수를 탐색할 때 조건을 추가했다.

3. 노란색 격자 영역 검증

가로와 세로가 결정되었을 때, 노란색 영역의 크기를 계산해 조건에 맞는지 확인했다.

• 노란색 영역:
• yellow = (width - 2) * (height - 2)

4. 조건에 맞는 결과 반환

위 조건을 만족하면 가로와 세로를 배열로 반환했다.

function solution(brown, yellow) {
    const total = brown + yellow; 

    for (let height = 3; height <= Math.sqrt(total); height++) {
        if (total % height === 0) { 
            const width = total / height; 

            if ((width - 2) * (height - 2) === yellow) {
                return [width, height]; 
            }
        }
    }
}

 

5. 트러블 슈팅. 

if ((width - 2) * (height - 2) === yellow) {
                return [width, height]; 
            }

 

이 부분에서 width - 2, height -2 이 부분에 괄호를 쳐주지 않으면 제대로 계산이 되지 않는다. 이 부분은 프리티어로도 해결이 되지 않는 문제기 때문에, 수동으로 괄호를 씌워줘야만 했다.