문제 개요
상자들의 크기가 담긴 배열이 주어졌을 때, 다음 조건에 따라 상자를 서로 포개서 보관하려고 합니다.
조건: 큰 상자의 크기가 작은 상자의 크기의 최소 2배 이상일 경우에만, 작은 상자를 큰 상자 안에 넣을 수 있습니다.
이렇게 상자를 모두 포개고 난 후, 겉으로 보이는 상자의 개수를 구하는 것이 이 문제의 목표입니다. 예시를 통해 살펴보겠습니다.
입력 : arr[] = { 1, 3, 4, 5 }
출력 : 3
→ 크기가 1인 상자를 크기가 3인 상자 안에 넣으면,
나머지 상자들은 각각 따로 보여야 하므로 총 3개가 됩니다.
입력 : arr[] = { 4, 2, 1, 8 }
출력 : 1
→ 1 → 2 → 4 → 8 순서로 차례대로 포개면
모든 상자가 하나의 상자 안에 들어가므로 1개만 보입니다.해결 접근 방식
이 문제는 정렬(Sorting)과 큐(Queue)를 활용한 그리디(Greedy) 기법으로 효율적으로 해결할 수 있습니다. 접근 과정은 다음과 같습니다.
먼저 배열을 오름차순으로 정렬합니다. 그다음 가장 작은 요소부터 큐에 삽입하고, 배열을 순회하면서 다음 규칙을 적용합니다.
- 현재 처리 중인 상자의 크기가 큐의 맨 앞(front)에 있는 상자 크기의 2배 이상이라면, 그 앞 상자는 현재 상자 안에 넣을 수 있으므로 큐에서 제거(pop)합니다.
- 그리고 현재 상자를 큐에 삽입(push)합니다.
배열 순회가 끝난 뒤 큐에 남아 있는 요소의 개수가 곧 보이는 상자의 개수(정답)가 됩니다. 정렬된 상태에서 탐욕적으로 매칭하기 때문에, 각 상자가 가능한 한 많은 작은 상자를 흡수하게 되어 최적의 결과를 얻을 수 있습니다.
C++ 코드 예제
#include <bits/stdc++.h>
using namespace std;
int main(){
int arr[] = { 1, 2, 3, 4, 5, 6 }; // 상자 크기가 담긴 배열
int n = sizeof(arr) / sizeof(arr[0]); // 배열의 크기
queue<int> q;
sort(arr, arr + n); // 배열 오름차순 정렬
q.push(arr[0]); // 가장 작은 요소를 먼저 큐에 삽입
for (int i = 1; i < n; i++) { // 배열 순회
int curr = q.front(); // 큐의 맨 앞 요소
if (arr[i] >= 2 * curr) // 현재 상자가 맨 앞 상자의 2배 이상이면
q.pop(); // 맨 앞 상자를 큐에서 제거
q.push(arr[i]); // 현재 상자를 큐에 삽입
}
cout << q.size() << "\n"; // 정답 출력
return 0;
}
실행 결과
3
위 코드에서 입력 배열 { 1, 2, 3, 4, 5, 6 }의 경우, 크기 1인 상자가 크기 2인 상자 안에 들어가고, 나머지 상자들은 각각 독립적으로 보이게 되므로 정답은 3이 됩니다.
시간 복잡도 분석
이 알고리즘의 시간 복잡도는 정렬 단계가 지배적이므로 O(N log N)입니다. 배열 순회와 큐 연산 자체는 각 요소당 O(1)의 비용으로 처리되며, 전체적으로 매우 효율적인 성능을 보입니다.
마무리
이번 글에서는 하나의 상자를 다른 상자에 넣은 후 보이는 상자의 개수를 찾는 문제를 다루었습니다. 정렬과 큐를 결합한 그리디 접근 방식을 통해 문제를 깔끔하게 해결하는 C++ 프로그램까지 함께 살펴보았습니다. 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 구현할 수 있습니다. 이 글이 여러분의 문제 해결에 도움이 되기를 바랍니다.