카펫

https://school.programmers.co.kr/learn/courses/30/lessons/42842?language=java

프로그래머스

문제 설명

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

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

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

제한사항

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

풀이

import java.util.ArrayList;

class Solution {
    public int[] solution(int brown, int yellow) {
        int a = brown + yellow;
        ArrayList<Integer> dlist = new ArrayList<>();

        // a의 약수를 모두 찾기
        for (int i = 1; i <= a; i++) {  
            if (a % i == 0) {
                dlist.add(i);
            }
        }

        // 약수 조합 중 조건을 만족하는 쌍을 찾기
        int[] result = findValidCombination(dlist, a, yellow);
        if (result != null) {
            return result;
        } else {
            return new int[2];
        }

    }

    // 조건을 만족하는 쌍 찾기 함수
    public int[] findValidCombination(ArrayList<Integer> dlist, int a, int yellow) {
        for (int i = 0; i < dlist.size(); i++) {
            int width = dlist.get(i);
            int height = a / width;

            // brown이 사방을 감싸고 있는 조건 체크
            if ((width - 2) * (height - 2) == yellow) {
                return new int[]{Math.max(width, height), Math.min(width, height)};
            }
        }
        return null;
    }
}

재귀를 사용하여 풀려고 함수도 만들고 접근했는데 필요없는 문제였다. 기본적으로 노랜색 카펫들은 갈색 카펫에 감싸질 것이므로 합한 개수의 크기를 가지는 하나의 큰 카펫으로 생각하고 이를 이루는 길이와 높이를 배열에 담으면 되겠다는 생각으로 구현하기 시작했다. 우선 큰 카펫의 길이와 높이가 될수 있는 약수들을 구하여 dlist 리스트에 저장해주었다. findValidCombination함수를 만들어 주었는데 dlist와 a, yellow를 매개변수로 받아서 이렇게 저장된 약수들 중 곱이 카펫의 넓이가 되는 조건과 갈색카펫이 감싸고 있는 조건인 (길이 -2) * (높이-2) 가 노란색개수와 같을 경우를 만족하면 배열에 내림차순으로 저장, 리턴해주고 만족하는 경우가 없으면 null을 리턴해주도록 구현하였다. 메인에서 이 함수를 호출하고 null일 경우에는 빈 배열을 null이아니라 만족하는 값이 있으면 해당 result배열을 출력하도록 하여 구현할 수 있었다.