- 명함 지갑을 만드는 회사에서 지갑의 크기를 정하려고 합니다. 다양한 모양과 크기의 명함들을 모두 수납할 수 있으면서, 작아서 들고 다니기 편한 지갑을 만들어야 합니다. 이러한 요건을 만족하는 지갑을 만들기 위해 디자인팀은 모든 명함의 가로길이와 세로 길이를 조사했습니다. 아래 표는 4가지 명함의 가로길이와 세로 길이를 나타냅니다.
<하단의 표 1을 참고합니다> - 가장 긴 가로 길이와 세로 길이가 각각 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 이하인 자연수입니다.
💡 해당 문제의 요점은 ‘브루트 포스’ 알고리즘을 통해 ‘카드의 사이즈를 구하기 위해서 모든 경우의 수를 다 확인’하여서 결과를 찾는다는 점입니다.
[STEP1] 2차원 배열을 1차원 배열로 분해하여 순회합니다(* 카드의 모든 경우의 수를 순회합니다)
[STEP2] 카드의 가로와 세로의 길이 중 ‘최대값’을 구하고 이전 카드의 너비와 비교하여 ‘최대값’을 구합니다.
[STEP3] 카드의 가로와 세로의 길이 중 ‘최소값’을 구하고 이전 카드의 높이와 비교하여 ‘최대값’을 구합니다.
[STEP4] 최종적으로 계산된 너비와 높이값을 구하여 최종 카드 사이즈를 구한다.
/**
* [완전탐색-1 : 브루트 포스] 13. 최소 직사각형
* 조건에 만족하는 모든 경우를 탐색하여 원하는 결과를 얻는 브루트 포스를 이용한 문제
*
* @return ResponseEntity
* @link ...
* @since 2023.07.23
*/@GetMapping("/exhausSearch1")public ResponseEntity<apiresponse> question13() {
intanswer=0;
int[][] size = {{60, 50}, {30, 70}, {60, 30}, {80, 40}};
intwidth=0; // 총 계산된 카드의 너비intheight=0; // 총 계싼된 카드의 높이// [STEP1] 2차원 배열을 1차원 배열로 순회합니다. (* 카드의 모든 경우를 순회합니다.)for (int[] card : size) {
intcardItemWidth= card[0]; // n번 명함의 가로 길이intcardItemHeight= card[1]; // n번 명함의 세로 길이// [STEP2] 카드의 기로와 세로의 길이 중 최대 값과 이전 카드 사이즈를 비교하여 최종 너비값을 구합니다.
width = Math.max(width, Math.max(cardItemWidth, cardItemHeight));
// [STEP3] 카드의 가로와 세로의 길이 총 최소 값과 이전에 카드 사이즈를 비교하여 최종 높이값을 구합니다.
height = Math.max(height, Math.min(cardItemWidth, cardItemHeight));
}
// [STEP4] 최종적으로 계산된 너비와 높이 값을 곱하여 결과값을 구합니다.
answer = width * height;
ApiResponsear= ApiResponse
.builder()
.result(answer)
.resultCode(SUCCESS_CODE)
.resultMsg(SUCCESS_MSG).build();
returnnewResponseEntity<>(ar, HttpStatus.OK);
}
</apiresponse
- 네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다행히 지도 암호를 해독할 방법을 적어놓은 메모도 함께 발견했다. 지도는 한 변의 길이가 n인 정사각형 배열 형태로, 각 칸은 "공백"(" ") 또는 "벽"("#") 두 종류로 이루어져 있다. 전체 지도는 두 장의 지도를 겹쳐서 얻을 수 있다. 각각 "지도 1"과 "지도 2"라고 하자. 지도 1 또는 지도 2 중 어느 하나라도 벽인 부분은 전체 지도에서도 벽이다. 지도 1과 지도 2에서 모두 공백인 부분은 전체 지도에서도 공백이다."지도 1"과 "지도 2"는 각각 정수 배열로 암호화되어 있다. 암호화된 배열은 지도의 각 가로줄에서 벽 부분을 1, 공백 부분을 0으로 부호화했을 때 얻어지는 이진수에 해당하는 값의 배열이다.
<하단의 사진 확인>
네오가 프로도의 비상금을 손에 넣을 수 있도록, 비밀지도의 암호를 해독하는 작업을 도와줄 프로그램을 작성하라.
[문제 설명] 하단의 사진
💡 입력 형식
- 입력으로 지도의 한 변 크기 n과 2개의 정수 배열 arr1, arr2가 들어온다.
1. 1 ≦ n ≦ 16
2. arr1, arr2는 길이 n인 정수 배열로 주어진다.
3. 정수 배열의 각 원소 x를 이진수로 변환했을 때의 길이는 n 이하이다. 즉, 0 ≦ x ≦ 2n - 1을 만족한다.
- Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.
<아래의 사진 참고>
Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다. Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.
💡 제한사항
- 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다. 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.
