본문 바로가기
알고리즘 문제 풀이/그리디

Number Of Rectangles That Can Form The Largest Square

by 가나무마 2021. 4. 6.
728x90

문제 링크

주어진 사각형을 자를 수만 있을 때 최대 넓이인 정사각형의 갯수를 구하라.
접근법 : 사각형의 길이를 늘릴 순 없고 자를 수만 있으므로 최소 길이인 변의 길이로 자른 게 해당 사각형의 최대 넓이임.
즉, 사각형이 있으면 최소 변의 길이를 구합니다.
그 변의 길이가 사각형 중에서 제일 큰 사각형이 우리가 구하고자하는 사각형입니다.
해당하는 정사각형과 넓이가 같은 사각형의 갯수를 구합니다.

내가 푼 방법

class Solution {
    public int countGoodRectangles(int[][] rectangles) {
        int answer = 0;            //최대 넓이를 가진 도형의 갯수.
        int max = 0;            //최대 넓이 도형 길이.
        for (int i = 0; i < rectangles.length; i++) {
            //변 중에서 제일 짧은 변의 길이를 구함.
            int temp = Math.min(rectangles[i][0],rectangles[i][1]);        

            if (temp > max) {        //변의 길이가 최댓값보다 크면
                max = temp;            //최댓값은 새로 구한 변의 길이.
                answer = 1;            //최댓값의 기준이 바꼈으므로 갯수는 1부터 다시 시작.
            } else if (temp == max) {    //변의 길이가 최댓값과 같으면
                answer++;                //최대 넓이를 가진 도형의 갯수가 1 증가.
            }
        }

        return answer;
    }
}

리트코드에 올라온 답안

public int countGoodRectangles(int[][] rectangles) {
        int cnt = 0, mx = 0;
        for (int[] rec : rectangles) {
            int side = Math.min(rec[0], rec[1]);
            if (side > mx) {
                cnt = 1;
                mx = side;
            }else if (side == mx) {
                ++cnt;
            }
        }
        return cnt;
}

Enhanced for문 사용한 것 빼곤 차이점이 딱히 없다.
밑에 코드가 확실히 가독성이 좋긴 함.

Kotlin 연습용 코드

class Solution {
    fun countGoodRectangles(rectangles:Array<IntArray>):Int {
        var answer = 0;
        var max = 0;

        rectangles.forEach {
            var temp = Math.min(it[0],it[1])
            if (temp > max) {
                max = temp
                answer = 1
            } else if (temp == max) {
                answer++
            }
        }

        return answer
    }
}
728x90
반응형

'알고리즘 문제 풀이 > 그리디' 카테고리의 다른 글

942. DI String Match  (0) 2021.08.11
561. Array Partition I  (0) 2021.07.25
1710. Maximum Units on a Truck  (0) 2021.06.23
Minimum Subsequence in Non-Increasing Order  (0) 2021.04.08
Split a String in Balanced Strings  (0) 2021.04.06