[TIL] 최소직사각형(JAVA)

https://school.programmers.co.kr/learn/courses/30/lessons/86491

프로그래머스

 

[간단 문제 설명]

사이즈가 모두 다른 명함들이 sizes[ ][ ] 배열로 주어진다.

이 명함들이 모두 들어갈 수 있는 가장 작은 사이즈의 지갑을 만들어야한다.

---

 

[처음 풀이 방식(정렬 사용)]

문제에서 좀 어려웠던 포인트는 명함을 가로/세로 방향으로 돌려서 명함에 수납할 수 있다는 것이다.

이는 즉 명함의 가로-세로 방향이 서로 뒤바뀔 수 있음을 의미한다.

 

그래서 명함의 더 긴 부분을 따로 저장하는 배열 longs[ ]과

명함의 더 짧은 부분을 따로 저장하는 배열 shorts[ ]를 선언했다.

그리고 명함의 가로-세로 길이 중 더 긴 부분은 배열 longs에 더 짧은 부분은 배열 shorts에 저장했다.

 

이후 두 배열(longs, shorts)를 정렬해서 가장 큰 값들만 골라서 지갑의 사이즈를 구하였다.

 

[정리]

1. 명함의 가로-세로 길이 중 긴 부분은 배열 longs[ ]에 짧은 부분은 배열 shorts[ ]에 저장

2. 배열 longs[ ], shorts[ ]를 정렬

3. 각 배열에서 가장 큰 값을 골라 곱함

 

import java.util.*;
class Solution {
    public int solution(int[][] sizes) {
        int answer = 0, len=sizes.length;
        int[] longs=new int[len];
        int[] shorts=new int[len];
        for(int i=0; i<len; i++){ // 명함에서 긴 부분은 longs에, 짧은 부분은 shorts에 저장
            if(sizes[i][0]>sizes[i][1]){
                longs[i]=sizes[i][0];
                shorts[i]=sizes[i][1];
            }else{
                longs[i]=sizes[i][1];
                shorts[i]=sizes[i][0];
            }
        }
        
        //배열 정렬
        Arrays.sort(longs);
        Arrays.sort(shorts);
        
        answer=longs[len-1]*shorts[len-1];//두 배열에서 가장 큰 값을 서로 곱함
        return answer;
    }
}

 

정렬을 사용한 코드의 채점을 돌려봤다.

모든 케이스를 통과할 수 있었지만, 뒤로 갈 수록 효율이 떨어진다..

---

[개선된 풀이 방식(Math.max() 사용)]

풀이 방법은 처음과 같다. 

다만 이번에는 longs와 shorts에서 최댓값을 구하기 위해 Math.max()를 사용했다.

하나의 배열을 만들어서 정렬하는 방식은, 배열의 원소가 늘어날 수록 효율이 떨어진다.

하지만 애초에 저장할 때부터 더 큰값을 변수에 저장한다면? 아무래도 훨씬 효율적일 것이다.

 

import java.util.*;
class Solution {
    public int solution(int[][] sizes) {
        int answer = 0, len=sizes.length;
        int longs=0,shorts=0;
        for(int i=0; i<len; i++){
            if(sizes[i][0]>sizes[i][1]){
                longs=Math.max(sizes[i][0],longs);
                shorts=Math.max(shorts,sizes[i][1]);
            }else{
                longs=Math.max(longs,sizes[i][1]);
                shorts=Math.max(shorts,sizes[i][0]);
            }
        }
        
        answer=longs*shorts;
        return answer;
    }
}

 

왜 진작에 이 생각을 못 했을까? 

고정관념에 사로잡히지 않도록 주의해야겠다.

정확성 테스트 결과를 보면 이전 코드에 비해 속도가 유의미하게 빨라진 것을 확인할 수 있었다.