C++에서 두 번째 배열을 재배열해 만들 수 있는 사전순 최소 수열 찾기

문제 개요

n개의 숫자로 이루어진 두 배열 A와 B가 주어졌다고 가정해 봅시다. 배열 B의 요소들을 스스로 안에서 재배열했을 때, (A[i] + B[i]) % n으로 계산되는 수열이 사전순(lexicographically)으로 가장 작아지도록 만들어야 합니다. 최종적으로 이렇게 얻을 수 있는 사전순 최소 수열을 반환하면 됩니다.

예를 들어 입력이 A = {1, 2, 3, 2}, B = {4, 3, 2, 2}라면, 출력은 [0, 0, 1, 2]가 됩니다.

접근 방법

이 문제는 그리디(Greedy) 기법으로 해결할 수 있습니다. 각 인덱스 i마다 아직 사용하지 않은 B의 요소 중에서 (A[i] + B[i]) % n의 결과를 최소로 만드는 값을 선택하는 것입니다.

(a + b) % n의 값을 최소화하기 위해서는 다음 두 가지 경우를 고려해야 합니다.

b가 n − a 이상인 값 중 가장 작은 값을 고르면 (a + b) % n = a + b − n이 되어 0에 가장 가까운 결과를 얻을 수 있습니다.
만약 b ≥ n − a를 만족하는 값이 하나도 없다면, 나머지 연산에서 값이 다시 0부터 순환하므로 집합에 남아 있는 가장 작은 값을 사용하는 것이 최선입니다.

이러한 탐색을 효율적으로 수행하기 위해 정렬된 set의 lower_bound() 함수와, 각 값의 빈도를 관리하는 unordered_map을 함께 활용합니다.

알고리즘 단계

n을 배열 a의 크기로 초기화합니다.
B의 각 요소 빈도를 저장할 맵(my_map)과 고유 값을 관리할 집합(my_set)을 정의합니다.
배열 b를 순회하며 각 요소의 빈도를 증가시키고 집합에 삽입합니다.
결과를 담을 sequence 배열을 선언합니다.
i = 0부터 n−1까지 순회하며 다음을 반복합니다.
- a[i]가 0인 경우: 집합에서 0 이상인 첫 번째 원소(lower_bound(0))를 꺼내 value % n을 sequence 끝에 추가합니다.
- a[i]가 0이 아닌 경우: x = n − a[i]를 계산한 뒤, 집합에서 x 이상인 첫 번째 원소를 찾습니다. 만약 그런 원소가 없다면(it == end), 집합의 최솟값(lower_bound(0))을 대신 사용합니다. 이후 (a[i] + value) % n을 sequence 끝에 추가합니다.
- 선택한 value의 빈도를 1 감소시키고, 빈도가 0이 되면 집합에서 해당 값을 삭제합니다.
완성된 sequence를 반환합니다.

C++ 구현 예제

아래 구현을 통해 더 잘 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;

// 벡터를 [a, b, c] 형태로 출력하는 함수
void print_vector(vector<auto> v) {
    cout << "[";
    for (int i = 0; i < v.size(); i++) {
        cout << v[i];
        if (i != v.size() - 1)
            cout << ", ";
    }
    cout << "]" << endl;
}

vector<int> solve(vector<int>& a, vector<int>& b) {
    int n = a.size();
    unordered_map<int, int> my_map; // 각 값의 빈도 저장
    set<int> my_set;                // 남아 있는 고유 값 관리 (항상 정렬됨)

    // B의 모든 요소를 맵과 집합에 등록
    for (int i = 0; i < n; i++) {
        my_map[b[i]]++;
        my_set.insert(b[i]);
    }

    vector<int> sequence;

    for (int i = 0; i < n; i++) {
        if (a[i] == 0) {
            // a[i]가 0이면 가장 작은 값을 그대로 사용
            auto it = my_set.lower_bound(0);
            int value = *it;
            sequence.push_back(value % n);
            my_map[value]--;
            if (!my_map[value])
                my_set.erase(value);
        } else {
            // (a[i] + b) % n을 최소화하려면 b = n - a[i] 이상인 최소값 탐색
            int x = n - a[i];
            auto it = my_set.lower_bound(x);
            if (it == my_set.end())
                it = my_set.lower_bound(0); // 없으면 최솟값으로 순환
            int value = *it;
            sequence.push_back((a[i] + value) % n);
            my_map[value]--;
            if (!my_map[value])
                my_set.erase(value);
        }
    }
    return sequence;
}

int main() {
    vector<int> a = {1, 2, 3, 2};
    vector<int> b = {4, 3, 2, 2};
    vector<int> res = solve(a, b);
    print_vector(res);
}

실행 결과

입력:

{1, 2, 3, 2}, {4, 3, 2, 2}

출력:

[0, 0, 1, 2]

동작 과정 살펴보기

위 예제(n = 4)에서 각 단계가 어떻게 진행되는지 확인해 보겠습니다.

i = 0: a[0] = 1이므로 x = 3을 찾습니다. 집합 {2, 3, 4}에서 3을 선택 → (1 + 3) % 4 = 0
i = 1: a[1] = 2이므로 x = 2를 찾습니다. 집합 {2, 3, 4}에서 2를 선택 → (2 + 2) % 4 = 0
i = 2: a[2] = 3이므로 x = 1을 찾습니다. 집합 {2, 4}에서 1 이상인 최솟값 2를 선택 → (3 + 2) % 4 = 1
i = 3: a[3] = 2이므로 x = 2를 찾지만, 집합 {4}에 없으므로 최솟값 4를 선택 → (2 + 4) % 4 = 2

결과적으로 [0, 0, 1, 2]라는 사전순 최소 수열을 얻을 수 있습니다.

복잡도 분석

set의 lower_bound, 삽입, 삭제 연산은 각각 O(log n)의 시간이 소요되므로, 전체 알고리즘의 시간 복잡도는 O(n log n)입니다. 공간 복잡도는 맵과 집합을 저장하는 데 O(n)이 필요합니다.