C++에서 Q번째 사람이 받는 최대 막대 길이 구하기

문제 설명

n개의 막대 길이가 배열로 주어집니다. 어떤 사람이 막대를 하나 선택하면, 현재 가장 긴 막대의 절반((max + 1) / 2)을 할당받고, 남은 부분((max − 1) / 2)은 다시 되돌려 놓습니다. 막대는 항상 충분하다고 가정할 때, 배열 q[]로 주어지는 M개의 쿼리에 대해 각 qi번째 사람(1부터 시작하는 유효한 번호)이 받게 될 가장 긴 막대의 길이를 구하는 것이 목표입니다.

예시

입력 : a[] = {6, 5, 9, 10, 12}
q[] = {1, 3}
출력 : 12 9
첫 번째 사람은 최대 길이인 12를 받습니다.
배열에서 12를 제거하고 (12 − 1) / 2 = 5를 다시 넣습니다.
두 번째 사람은 최대 길이인 10을 받습니다.
(10 − 1) / 2 = 4를 다시 넣습니다.
세 번째 사람은 최대 길이인 9를 받습니다.

입력 배열이 {6, 5, 9, 10, 12}이고 쿼리 배열이 {1, 3}이라면 출력은 12와 9가 됩니다. 그 과정은 다음과 같습니다.

첫 번째 사람은 가장 긴 막대인 12를 받습니다.
배열에서 12를 제거하고 (12 − 1) / 2 = 5를 다시 넣습니다.
두 번째 사람은 이 시점에서 가장 긴 막대인 10을 받습니다.
(10 − 1) / 2 = 4를 다시 넣습니다.
세 번째 사람은 가장 긴 막대인 9를 받습니다.

알고리즘

매 단계마다 전체를 다시 정렬하는 대신, 스택과 큐 두 자료구조를 활용하면 효율적으로 해결할 수 있습니다. 스택에는 아직 잘리지 않은 원본 막대를 내림차순으로 보관하고, 큐에는 잘린 후 남은 조각들을 순서대로 보관합니다.

모든 막대 길이를 오름차순으로 정렬한 뒤 스택에 차례로 push합니다. 이렇게 하면 가장 긴 막대가 항상 스택의 top에 위치하게 됩니다.
큐가 비어 있으면 스택의 top 값을 꺼내 결과에 기록하고, 그 절반(top / 2)이 0이 아니면 큐에 push합니다.
스택이 비어 있으면 큐의 front 값을 꺼내 결과에 기록하고, 그 절반(front / 2)이 0이 아니면 다시 큐에 push합니다.
둘 다 비어 있지 않으면 스택의 top과 큐의 front를 비교하여 더 큰 값을 꺼내 결과에 기록하고, 그 절반을 큐에 push합니다.
스택과 큐가 모두 빌 때까지 위 과정을 반복하면, i번째 사람이 받는 막대 길이가 순서대로 결과 벡터에 채워집니다.

이 방식이 올바르게 동작하는 이유는, 새로 큐에 들어가는 조각은 항상 이전에 처리된 값보다 작거나 같기 때문에 큐 안의 값들도 자연스럽게 감소하는 순서를 유지하기 때문입니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
vector<int> getMaxRodLength(int *arr, int n, int m) {
    queue<int> q;
    sort(arr, arr + n);
    stack<int> s;
    for (int i = 0; i < n; ++i) {
        s.push(arr[i]);
    }
    vector<int> result;
    while (!s.empty() || !q.empty()) {
        int val;
        if (q.empty()) {
            val = s.top();
            result.push_back(val);
            s.pop();
            val = val / 2;
            if (val) {
                q.push(val);
            }
        } else if (s.empty()) {
            val = q.front();
            result.push_back(val);
            q.pop();
            val = val / 2;
            if (val != 0) {
                q.push(val);
            }
        } else {
            val = s.top();
            int fr = q.front();
            if (fr > val) {
                result.push_back(fr);
                q.pop();
                fr = fr / 2;
                if (fr) {
                    q.push(fr);
                }
            } else {
                result.push_back(val);
                s.pop();
                val = val / 2;
                if (val) {
                    q.push(val);
                }
            }
        }
    }
    return result;
}
int main() {
    int rods = 5;
    int queries = 10;
    int arr[rods] = {6, 5, 9, 10, 12};
    vector<int> result = getMaxRodLength(arr, rods, queries);
    int query[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int n_query = sizeof(query) / sizeof(query[0]);
    cout << "Rod length = ";
    for (int i = 0; i < n_query; ++i) {
        cout << result[query[i] - 1] << " ";
    }
    cout << endl;
    return 0;
}

실행 결과

위 프로그램을 컴파일하고 실행하면 다음과 같은 출력이 생성됩니다.

Rod length = 12 10 9 6 6 5 5 4 3 3

복잡도 분석

시간 복잡도: 초기 정렬에 O(n log n)이 소요되며, 이후 각 막대는 길이가 1이 될 때까지 계속 절반으로 잘리므로 전체 조각 수는 약 n × log₂(maxLen)개입니다. 따라서 전체 시간 복잡도는 O(n log n + n log(maxLen))입니다.
공간 복잡도: 스택, 큐, 결과 벡터에 조각들을 저장하므로 O(n + n log(maxLen))입니다.