99클럽 2기 | 자바 | 비기너
KDT 실무형 스프링 백엔드 엔지니어 양성과정 6기 | Algorithm CODEKATA
🔲 최소 직사각형
🏷 관련 주제 : 완전 탐색
문제 설명
명함 지갑을 만드는 회사에서 지갑의 크기를 정하려고 합니다.
다양한 모양과 크기의 명함들을 모두 수납할 수 있으면서,
작아서 들고 다니기 편한 지갑을 만들어야 합니다.
이러한 요건을 만족하는 지갑을 만들기 위해
디자인팀은 모든 명함의 가로 길이와 세로 길이를 조사했습니다.
아래 표는 4가지 명함의 가로 길이와 세로 길이를 나타냅니다.
| 명함 번호 | 가로 길이 | 세로 길이 |
|---|---|---|
| 1 | 60 | 50 |
| 2 | 30 | 70 |
| 3 | 60 | 30 |
| 4 | 80 | 40 |
가장 긴 가로 길이와 세로 길이가 각각 80, 70이기 때문에 80(가로) x 70(세로) 크기의 지갑을 만들면 모든 명함들을 수납할 수 있습니다.
하지만 2번 명함을 가로로 눕혀 수납한다면
80(가로) x 50(세로) 크기의 지갑으로 모든 명함들을 수납할 수 있습니다.
이때의 지갑 크기는 4000(=80 x 50)입니다.
모든 명함의 가로 길이와 세로 길이를 나타내는 2차원 배열 sizes가 매개변수로 주어집니다.
모든 명함을 수납할 수 있는 가장 작은 지갑을 만들 때,
지갑의 크기를 return 하도록 solution 함수를 완성해주세요.
제한사항
sizes의 길이는 1 이상 10,000 이하입니다.sizes의 원소는[w, h]형식입니다.w는 명함의 가로 길이를 나타냅니다.h는 명함의 세로 길이를 나타냅니다.w와h는 1 이상 1,000 이하인 자연수입니다.
입출력 예
| sizes | result |
|---|---|
| [[60, 50], [30, 70], [60, 30], [80, 40]] | 4000 |
| [[10, 7], [12, 3], [8, 15], [14, 7], [5, 15]] | 120 |
| [[14, 4], [19, 6], [6, 16], [18, 7], [7, 11]] | 133 |
입출력 예 설명
입출력 예 #1
문제 예시와 같습니다.
입출력 예 #2
명함들을 적절히 회전시켜 겹쳤을 때,
3번째 명함(가로: 8, 세로: 15)이 다른 모든 명함보다 크기가 큽니다.
따라서 지갑의 크기는 3번째 명함의 크기와 같으며, 120(=8 x 15)을 return 합니다.
입출력 예 #3
명함들을 적절히 회전시켜 겹쳤을 때,
모든 명함을 포함하는 가장 작은 지갑의 크기는 133(=19 x 7)입니다.
✔ Solution with Brute Force
class Solution {
public int solution(int[][] sizes) {
int answer = 0;
int w = 0;
int h = 0;
int len = sizes.length;
for (int i = 0; i < len; i++) {
w = Math.max(w, Math.max(sizes[i][0],sizes[i][1]));
h = Math.max(h, Math.min(sizes[i][0],sizes[i][1]));
}
answer = w * h;
return answer;
}
}채점 결과
💥 어떤 문제가 있었고, 나는 어떤 시도를 했는지💦
- 이차원 배열
sizes가 매개변수로 주어져서 값들을 어떻게 비교할지 고민함. sizes배열 안 일차원 배열의 원소가i번 인덱스는 가로 j번 인덱스는 세로같이 고정된 것이 아니라서 명함을 돌리는 것을 고려하는 방법이 어려웠다.- 비교하는 것을 어떤 코드로 쓸지 고민: 생각나는 코드 다 써 봄.
어떻게 해결했는지👍
너비
w를 모든 원소 중 최대 길이로 할당하고 높이h를 나머지 변의 길이 중 최댓값으로 할당하기로 결정
(∵w를 모든 원소 중 최대 길이로 할당하면w보다 작은 길이는 모두 담을 수 있음.
지갑을 최대한 작게 만들기 위한 조건,h가 최대한 작아야 함.
따라서 명함의 가로, 세로 중 긴 쪽이 너비w쪽으로 가야h에는 명함의 짧은 쪽만 들어가서 최소값을 가질 수 있음.)저번에 for문을 돌릴 때, 계속 사용하는 변수는 값을 할당하여 반복문을 돌려도 된다고 하셨던 코드장(?)님의 말씀이 떠올라
sizes의 길이를 새로운 변수에 할당.int answer = 0; int w = 0; int h = 0; int len = sizes.length;명함을 돌리는 여부를 어떻게 고려할진 모르겠지만
일단 반복문으로 일차원 배열을 하나씩 꺼내보자.for (int i = 0; i < len; i++) { ... }일차원 배열의 원소를 비교하여 큰 값을 너비
w와 비교, 둘 중 큰 값을w에 다시 할당일차원 배열의 원소를 비교하여 작은 값을 높이
h와 비교, 둘 중 큰 값을h에 다시 할당
(여기서 if문을 여러번 써서 값을 비교해야할까?Math.max() Math.min()을 여러번 쓰는 것이 나을까? 고민하다가 둘 다 해 봄.)
if문을 여러번 쓰는 방법 채점 결과
if (sizes[i][0] >= sizes[i][1]) { if (sizes[i][0] > w) { w = sizes[i][0]; } if (sizes[i][1] > h) { h = sizes[i][1]; } } else { if (sizes[i][0] > h) { h = sizes[i][0]; } if (sizes[i][1] > w) { w = sizes[i][1]; } }채점 결과
if문 한번만 쓰고
max()min()메서드 사용하기 채점 결과if (sizes[i][0] >= sizes[i][1]) { w = Math.max(w, sizes[i][0]); h = Math.max(h, sizes[i][1]); } else { w = Math.max(w, sizes[i][1]); h = Math.max(h, sizes[i][0]); }채점 결과
max()min()메서드만 사용하기w = Math.max(w, Math.max(sizes[i][0], sizes[i][1])); h = Math.max(h, Math.min(sizes[i][0], sizes[i][1]));for문이 끝나면
answer에 직사각형의 넓이(w × h)를 할당answer = w * h;
💬 무엇을 새롭게 알았는지
Math.max()Math.mind()메서드는 따로 import를 해주지 않아도 되는구나.- if문을 이중으로 쓰더라도 속도가 많이 느려지지 않는구나.
- [Java 봐 | 알고리즘] 완전 탐색(링크🔗)
