개발자 Lim

조건:

• 1 <= area <= 107

의역: 웹 개발자는 웹 페이지를 만들 때 어떤 size로 만들어야 할지 알아야 합니다.

정수 area가 제공될 때 해당 정수 만큼의 넓이를 만들 수 있는 길이와 너비를 정수 배열로 만들어 반환해라. [길이, 너비]

단 (길이 >= 너비) 이여야 하고 길이와 너비의 차이는 가능한 제일 작아야 한다.  

의역: area = 4 일때 가능한 경우는 [1,4], [2,2], [4,1] 여기서 위에 나온 

"단 (길이 >= 너비) 이여야 하고 길이와 너비의 차이는 가능한 제일 작아야 한다." 라는 조건을 충족하는 요소는 

[2,2] 임으로 [2,2]를 반환한다.

<풀이>

1. 브루트 포스 (단순 반복문을 통해 모든 경우 체크)

class Solution {
    // 시간복잡도 O(n) 공간 복잡도 O(1)
    public int[] constructRectangle(int area) {
        int gap=Integer.MAX_VALUE;
        // 최소 length 길이
        int length=1;
        // 약수를 생각한다면 전체를 검사 할 필요 없이 /2 까지만 검사해도 ok
        for(int i=1;i<=area/2;i++){
            // 약수 라면
            if(area%i==0){
                // gap 차이가 적고 length(길이)가 너비 보다 크다면 length, gap 갱신
                if(Math.abs(area/i-i)<gap&&(area / i)>=i) {
                    length = area / i;
                    gap = area/i-i;
                }
            }
        }
        int ans[]={length,area/length};
        return ans;
    }
}

2. Math.squr()을 통해 정답에 가장 가까운 범위부터 탐색

+ 큰 값 보다는 작은 값을 찾는 방법을 써야 꼬이지 않는다.

해당 문제를 width 가 아닌 length를 구하는 식으로 짠 경우 0의 경우로 인해 큰 값이 아닌 작은 값이 나오는 문제가 생긴다.

class Solution {
    // 시간 복잡도 O(n) 공간 복잡도 O(1)
    public int[] constructRectangle1(int area) {
        int ans[] = new int[2];
        int width = (int)Math.sqrt(area);
        while(area%width!=0){
            width--;
        }
        ans[1] = width;
        ans[0] = area/width;

        return ans;
    }
}

링크: https://leetcode.com/problems/construct-the-rectangle/description/