상자의 크기를 포함하는 배열이 제공되는 문제를 해결하기 위해. 이제 더 큰 상자가 더 작은 상자 크기의 두 배 이상인 경우 더 큰 상자 안에 더 작은 상자를 넣을 수 있다는 조건이 주어졌습니다. 이제 예를 들어 보이는 상자의 수를 결정해야 합니다.
Input : arr[] = { 1, 3, 4, 5 }
Output : 3
Put a box of size 1 in the box of size 3.
Input : arr[] = { 4, 2, 1, 8 }
Output : 1 해결책을 찾기 위한 접근 방식
이 문제에서 우리의 접근 방식은 앞으로 나아갈 때 배열을 정렬하는 것입니다. 이제 요소를 대기열에 푸시합니다. 진행하면서 현재 요소가 큐의 앞 요소의 두 배보다 크거나 같은지 확인할 것입니다. 그것이 사실이라면, 우리는 지금 앞 요소를 팝합니다. 마지막으로 큐의 현재 요소를 푸시합니다. 우리의 대답은 마지막에 대기열의 크기입니다.
예시
#include <bits/stdc++.h>
using namespace std;
int main(){
int arr[] = { 1, 2, 3, 4, 5, 6 }; // given array containing the size of our boxes
int n = sizeof(arr) / sizeof(arr[0]); // size of our array
queue<int> q;
sort(arr, arr + n); // sorting our array
q.push(arr[0]); // pushing the smallest element in the front
for (int i = 1; i < n; i++) { // traversing the array
int curr = q.front(); // current element
if (arr[i] >= 2 * curr) // if the size of the current box is greater than twice
// of the box in front so we pop the front
q.pop();
q.push(arr[i]); // pushing the current element in the queue
}
cout << q.size() << "\n"; // our answer
return 0;
} 출력
3
결론
이 튜토리얼에서는 상자를 다른 상자 안에 넣은 후 보이는 상자의 수를 찾는 문제를 해결합니다. 우리는 또한 이 문제에 대한 C++ 프로그램과 이 문제를 해결하는 완전한 접근 방식(Normal)을 배웠습니다. C, Java, python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 튜토리얼이 도움이 되기를 바랍니다.