[Java/프로그래머스] 최소직사각형

문제

 

 

 

풀이

(1) 문제 분석하기

• 문제에 현혹되지 말자. 결국 긴 변 중에 가장 긴 변과 짧은 변 중에 가장 긴 별을 곱하면 된다.
• for문과 if문을 중첩으로 사용했더니 바로 시간초과가 나버렸다...!
  • 배열의 정렬을 이용해보자.
  • 최대수, 최소수를 구해주는 Math.max, Math.min을 이용해보자.

 

(2) 슈도코드 작성하기

// 첫번째 풀이
각 변을 담을 int 변수 biggerSideMax, smallerSideMax 선언
for(sizes의 길이만큼) {
	if(첫번째 요소가 두번째 요소보다 클 때) {
    	if(긴 변의 요소가 biggerSideMax 보다 클 때 {
        	biggerSideMax에 긴 변 요소 담기
        }
        if(짧은 변의 요소가 smallerSideMax보다 클 때) {
        	smallerSideMax에 짧은 변 요소 담기
        }
    } else {
    	긴 변과 짧은 변의 순서 바꿔주기
        i--
    }
}
biggerSideMax * smallerSideMax



// 두번째 풀이
긴 변이 담길 배열과 짧은 변이 담길 배열 선언
for(sizes의 길이만큼) {
	if(첫번째 요소가 두번째 요소보다 클 때) {
    	첫번째 요소를 긴 변 배열에 담기
        두번째 요소를 짧은 변 배열에 담기
    } else {
    	두번째 요소를 긴 변 배열에 담기
        첫번째 요소를 짧은 변 배열에 담기
    }
}
두 배열 모두 오름차순으로 정렬
각 배열의 마지막 요소만 출력
biggerSideMax * smallerSideMax



// 세번째 풀이
각 변을 담을 int 변수 biggerSideMax, smallerSideMax 선언
for(sizes의 길이만큼) {
	Math.max 메소드를 이용하여 긴 변을 구하고,
    Math.min 메소드를 이용하여 짧은 변을 구하기
}
biggerSideMax * smallerSideMax

 

 

(3) 코드 구현하기

 

시간초과 났던 첫번째 풀이

package algorithm.test14;

public class Solution {
    public static void main(String[] args) {
        int[][] arr = {{60, 50}, {30, 70}, {60, 30}, {80, 40}};
        System.out.println(solution(arr));
    }

    public static int solution(int[][] sizes) {
        // 긴 변중에 가장 긴 변
        // 짧은 변 중에 가장 긴 변

        // 첫번재 풀이
        int biggerSideMax = 0;
        int smallerSideMax = 0;
        for (int i = 0; i < sizes.length; i++) {
            if (sizes[i][0] > sizes[i][1]) {
                if (biggerSideMax < sizes[i][0]) {
                    biggerSideMax = sizes[i][0];
                }
                if (smallerSideMax < sizes[i][1]) {
                    smallerSideMax = sizes[i][1];
                }
            } else {
                int temp = sizes[i][0];
                sizes[i][0] = sizes[i][1];
                sizes[i][1] = temp;
                i--;
            }
        }
        return biggerSideMax * smallerSideMax;
    }
}

 

배열의 정렬을 이용한 두번째 풀이

package algorithm.test14;

import java.util.Arrays;

public class Solution {
    public static void main(String[] args) {
        int[][] arr = {{60, 50}, {30, 70}, {60, 30}, {80, 40}};
        System.out.println(solution(arr));
    }

    public static int solution(int[][] sizes) {
        // 긴 변중에 가장 긴 변
        // 짧은 변 중에 가장 긴 변

        // 두번째 풀이
        int[] firstArr = new int[sizes.length];
        int[] secondArr = new int[sizes.length];
        for (int i = 0; i < sizes.length; i++) {
            if (sizes[i][0] > sizes[i][1]) {
                firstArr[i] += sizes[i][0];
                secondArr[i] += sizes[i][1];
            } else {
                firstArr[i] += sizes[i][1];
                secondArr[i] += sizes[i][0];
            }
        }
        Arrays.sort(firstArr);
        Arrays.sort(secondArr);
        int biggerSideMax = firstArr[sizes.length - 1];
        int smallerSideMax = secondArr[sizes.length - 1];

        return biggerSideMax * smallerSideMax;
    }
}

 

Math.max, Math.min을 이용한 세번째 풀이

package algorithm.test14;

public class Solution {
    public static void main(String[] args) {
        int[][] arr = {{60, 50}, {30, 70}, {60, 30}, {80, 40}};
        System.out.println(solution(arr));
    }

    public static int solution(int[][] sizes) {
        // 긴 변중에 가장 긴 변
        // 짧은 변 중에 가장 긴 변

        // 세번째 풀이
        int biggerSideMax = 0, smallerSideMax = 0;
        for (int[] size : sizes) {
            biggerSideMax = Math.max(biggerSideMax, Math.max(size[0], size[1]));
            smallerSideMax = Math.max(smallerSideMax, Math.min(size[0], size[1]));
        }

        return biggerSideMax * smallerSideMax;
    }
}

 

 

 

 

프로그래머스