프로그래머스 [ 카펫 / Lv2 ] - JAVA

문제 링크

---

https://school.programmers.co.kr/learn/courses/30/lessons/42842

프로그래머스

 

 

문제 설명

---

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.

 

Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.

 

Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

 

제한사항

---

• 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
• 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
• 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

 

입출력 예

---

 

코드

---

class 카펫 {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];
        int yellowWidthPlusHeight = (brown / 2) - 2;

        for(int height = 1; height <= Math.sqrt(yellow); height++) {
            int width = yellowWidthPlusHeight - height;
            if(height * width == yellow) {
                answer[0] = width + 2;
                answer[1] = height + 2;
            }
        }
        return answer;
    }
}

 

알고리즘 설명

---

간단한 브루트 포스 알고리즘 문제입니다. 주어진 갈색 카펫과 노란색 카펫의 면적을 기반으로, 카펫의 가로와 세로 크기를 구합니다. 핵심은  노란색 카펫의 가로와 세로를 구한 뒤, 이를 기반으로 전체 카펫의 크기를 계산하는 것입니다.

 

코드 해석

---

yellow 카펫의 가로와 세로 길이를 더한 값은 (brown 카펫 외곽의 격자 개수 / 2) - 2로 구할 수 있습니다. 카펫의 가로 길이는 세로 길이보다 크거나 같기 때문에, 노란색 카펫의 세로 길이는 yellow의 제곱근보다 클 수 없습니다. 따라서 height를 1부터 yellow의 제곱근까지 탐색하며, 그에 맞는 가로 길이를 구합니다.