프로그래머스 Lv2 카펫 Java 완전탐색

문제설명

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

구현방법

• 약수를 이용한 완전탐색이다. 먼저 전체 넓이의 가로, 세로가 될 수 있는 값을 x,y로 하였고 전체넓이의 약수를 구하여 list에 저장한다. 단 yellow가 존재하는 한 가로, 세로의 길이는 반드시 3 이상이어야 하므로 1, 2와 그에 해당하는 값은 약수에서 제외시켰다.

• yellow부분의 가로, 세로는 a,b로 하였고 역시 약수를 구한다.

• x,y쌍을 하나씩 탐색하며 yellow가 존재하기 위한 조건(양쪽에 최소 1칸씩, 총 2칸이 존재해야 함) a<=x-2&& b<=y-2로 가능한 값이 있으면 그때 x,y값이 정답이다.

import java.util.*;
class Solution {
    public int[] solution(int brown, int yellow) {
        int total = brown+yellow;
        List<Integer> list = new ArrayList<>();
        for(int i=3;i<=Math.sqrt(total);i++){
           if(total%i==0){
               list.add(i);
           } 
        }
        int n = list.size();
        for(int i=n-1;i>=0;i--){
            list.add(total/list.get(i));
        }
        List<Integer> ylist = new ArrayList<>();
        for(int i=1;i<=Math.sqrt(yellow);i++){
           if(yellow%i==0){
               ylist.add(i);
           } 
        }
        n = ylist.size();
        for(int i=n-1;i>=0;i--){
            ylist.add(yellow/ylist.get(i));
        }
        int x=0;
        int y=0;
        int a=0;
        int b=0;
        n=list.size();
        Loop : for(int i=0;i<n/2;i++){
            x = list.get(n-i-1);
            y = list.get(i);
            int m = ylist.size();
            for(int j=0;j<m/2;j++){
                a= ylist.get(m-j-1);
                b = ylist.get(j);
                if(a<=x-2&&b<=y-2){
                    break Loop;
                }
            }
        }
        return new int[] {x,y};
    }
}