728x90
문제
명함의 가로, 세로 길이가 주어졌을 때
모든 명함을 담을 수 있는 가장 작은 명함 지갑의 넓이를 구하라
접근 방식
가로 세로
1 60 50
2 30 70
3 60 30
4 80 40
만약 명함의 길이가 위와 같이 주어졌다면
가로의 가장 긴 길이와 세로의 가장 긴 길이를 찾아
지갑을 만들면 모든 명함을 넣을 수 있다.
하지만 문제에서 구해야 하는 것은 지갑의 최소 넓이이기 때문에
생각을 좀 달리해야 한다.
가장 긴 가로와 세로 길이의 지갑이면 명함을 모두 넣을 수 있으니
명함을 90도 회전하는 경우에는 좀 더 작은 면적의 지갑으로도
명함을 모두 보관할 수 있다.
가로 세로
1 60 50
2 70 30
3 60 30
4 80 40
바로 위와 같이 가로보다 세로가 긴 경우 둘의 길이를 바꿔준 후에 (90도 회전)
가로와 세로의 가장 큰 값을 구하면 된다.
입력의 크기가 작은 문제이기 때문에 완전 탐색을 이용해
주어진 배열을 순회하며 가로와 세로의 길이를 확인한 후에
세로가 더 큰 경우 바꿔주고 각각의 최대 길이를 갱신해준다.
풀이
public class Main {
public static void main(String[] args) {
System.out.println(solution(
new int[][]{{60, 50}, {30, 70}, {60, 30}, {80, 40}}
));
System.out.println(solution(
new int[][]{{10, 7}, {12, 3}, {8, 15}, {14, 7}, {5, 15}}
));
System.out.println(solution(
new int[][]{{14, 4}, {19, 6}, {6, 16}, {18, 7}, {7, 11}}
));
}
private static int solution(int[][] sizes) {
int max1 = 0;
int max2 = 0;
for (int i = 0; i < sizes.length; i++) {
int left = sizes[i][0];
int right = sizes[i][1];
if (left > right) {
sizes[i][0] = right;
sizes[i][1] = left;
}
max1 = Math.max(sizes[i][1], max1);
max2 = Math.max(sizes[i][0], max2);
}
return max1 * max2;
}
}
'Java > Algorithms' 카테고리의 다른 글
[백준] 17478번 : 재귀함수가 뭔가요? (1) | 2023.10.24 |
---|---|
[프로그래머스] 모의고사 (1) | 2023.10.24 |
[백준] 11729번 : 하노이 탑 이동 순서 (1) | 2023.10.14 |
[백준] 1629번 : 곱셈 (1) | 2023.10.13 |
[백준] 11728번 : 배열 합치기 (0) | 2023.10.12 |