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

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

프로그래머스

 

ver.1

import java.util.*;

class Solution {
    public int solution(int[][] sizes) {
        List<Integer> list = new ArrayList<Integer>();
		int len = sizes.length;
 
		for(int i=0; i<len; i++) { 
			for(int j=0; j<len; j++) { 
				if(check(sizes, sizes[i][0], sizes[j][1])) {
					int num = sizes[i][0]*sizes[j][1];  
					list.add(num); 
				}
			}
		}
        Collections.sort(list);
		return list.get(0);
    }
    static boolean check(int[][] sizes, int width, int height) {
		int len   = sizes.length;
		
		int c=0;
		while(c<sizes.length) {
			if(width>=sizes[c][0] && height>=sizes[c][1]) {
				//카드가 지갑에 들어가는 경우
				c++;
				continue; //다음 카드를 확인한다.
			}else if(width>=sizes[c][1] && height>=sizes[c][0]) {
				//카드가 안들어가서 방향을 바꿔 넣어봄
				c++;
				continue;
			}else {
				return false; // 사이즈가 맞지 않는 카드가 있다는 의미
			}
		}
		return  true; //카드가 모두 들어갈 경우 
	}
}

기본 테스트 케이스는 통과했지만 case 4,6 오류, 19시간초과가 떴다.

 

[코드 설명]

너비와 높이에 들어갈 수 있는 모든 해를 구하고,  카드가 들어갈 수 있는지 확인한다.

들어가지 않으면 카드의 방향을 바꿔(너비 > 높이, 높이>너비) 들어가는지 확인한다.

 

[문제점]

너비와 높이의 값 설정할 때 (for문)

모든 경우의 수를 나타내지 못한다. 

예를 들어 sizes = [ [3,5], [6,2] ]일경우

  위 코드를 사용하면 지갑의 너비와 높이의 경우의 수는 

 1. (3,5)

 2. (3,2)

 3. (6,5)

 4. (6,2)

이고 정답으로 넓이: 30 (3번 6*5)이 나오지만 

실제 정답은 넓이: 18 ( [6,2]카드를 뒤집어 sizes = [ [3,5], [2,6] ]으로 만들고 지갑 사양을 3,6으로 함 ) 

---

넓이 = 가로 * 세로

가로 또는 세로의 길이를 최솟값으로 만들고,

각각의 최댓값을 구해 넓이를 구하는 방식으로 알고리즘을 다시 짰다.

Ver.2

import java.util.*;
class Solution {
    public int solution(int[][] sizes) {
      int len = sizes.length;

        for(int i=0; i<len; i++) {
            if(sizes[i][0]>sizes[i][1]) {
                int num     = sizes[i][0];
                sizes[i][0] = sizes[i][1];
                sizes[i][1] = num;
            }
        }

        Arrays.sort(sizes, (int[] a, int[] b) -> {
            if(a[0] < b[0])       return 1;
            else if(a[0] > b[0])  return -1;
            else                  return 0;
        });
        int num = sizes[0][0];
        Arrays.sort(sizes, (int[] a, int[] b) -> {
            if(a[1] < b[1])       return 1;
            else if(a[1] > b[1])  return -1;
            else                  return 0;
        });

        return num *= sizes[0][1];

    }
}

 

 

처음에는 DFS 공부 중이라 재귀를 이용해 풀어봤으나 실패

더 공부해서 DFS버전으로 풀어보고 싶다.