[완전탐색, 약수] 프로그래머스 level2 카펫 자바 풀이

프로그래머스 카펫 자바(java) 풀이

• Level 2
• 완전탐색
• 카펫
  
  
  

문제 정리

1. 카펫은 중앙에는 빨간색, 테두리 1줄은 갈색으로 칠해져 있었다.
2. 카펫의 갈색격자 수, 빨간색 격자 수는 알고 있다.
3. 카펫의 가로, 세로 크기를 순서대로 담아 return 하여라.
4. 카펫의 가로 길이 >= 세로길이
   
   
   

문제 풀이(Solution)

level2의 문제이지만 level1이 더 맞지 않나 생각합니다.

1. 카펫의 갈색의 개수와 빨간색의 개수를 더하여 카펫에서 총 격자의 개수를 구합니다.
2. 총 격자 개수의 약수의 쌍을 구합니다. brown=10, red=2 인 경우 총 격자의 개수는 12입니다.
   이때 카펫은 다음과 같이 가능합니다

   (1,12), (2,6), (3,4), (4,3), (6,2), (12,1)

   하지만 행의 길이가 3보다 작게 되면 가운데 빨간색 격자가 들어갈 수 없기 때문에 행의 길이가 3이상이어야 합니다.

3. (3,4)의 경우 3을 가로의 길(열)이 4를 세로의 길이(행)라고 합시다. 빨간색 격자의 행, 열의 길이는 테두리 길이가 2씩 빠지게 되므로 다음과 같습니다.

빨간색 격자의 행의 길이 = 4-2 = 2
빨간색 격자의 열의 길이 = 3-2 = 1
총 빨간색 격자의 수 = 2 x 1 = 2

4. 위에서 총 빨간색 격자의 길이를 구하였습니다. 주어진 수와 같으므로 (3,4)가 답이 될 수 있습니다. 여기서 가로와 세로의 길이만 비교합니다. 하지만 이는 세로의 길이가 더 기므로 답이될 수 없습니다. (4,3)이 답이 됩니다.

프로그래머스 카펫 자바 코드

import java.util.*;

class Solution {
    public static void main(String[] args) {
        int brown = 10;
        int red = 2;
        int[] ans = solution(brown, red);

        for(int i=0; i<ans.length; i++)
            System.out.println(ans[i]);;
    }

    public static int[] solution(int brown, int red) {
        int[] answer = {};
        int sum = brown + red;

        for(int i=3; i<=sum; i++){
            // 약수 모두 구하기
            if(sum % i == 0){
                int col = sum / i;    // 가로
                int row = sum / col;    // 세로

                int a = col - 2;    // 빨간색 격자의 가로
                int b = row - 2;    // 빨간색 격자의 세로
                if(a*b == red && col >= row){
                    return new int[]{col, row};
                }
            }
        }

        return answer;
    }
}