C++로 짝수·홀수 순서를 유지하며 만들 수 있는 가장 큰 수 구하기

문제 개요

이 문제에서는 숫자 배열이 주어지고, 특정 조건을 만족하도록 숫자들을 재배열하여 만들 수 있는 가장 큰 수를 찾아야 합니다. 핵심 제약 조건은 짝수끼리의 상대적 순서와 홀수끼리의 상대적 순서는 반드시 유지되어야 한다는 점입니다. 즉, 짝수들의 등장 순서나 홀수들의 등장 순서를 임의로 변경할 수 없습니다.

예시를 통해 개념을 더 자세히 살펴보겠습니다.

입력 : {17, 80, 99, 27, 14, 22}
출력 : 801799271422
설명 : 짝수와 홀수의 순서는 다음과 같습니다.
짝수 : 80 14 22
홀수 : 17 99 27

위 예시에서 99가 가장 큰 숫자이지만, 홀수 순서에서 17이 99보다 앞에 있으므로 17을 먼저 사용해야 합니다. 따라서 최종 배치는 80 → 17 → 99 → 27 → 14 → 22 순서가 되며, 결과값은 801799271422입니다.

접근 방법

문제를 이해했으니 해결 방법을 생각해 보겠습니다. 단순히 내림차순으로 정렬할 수는 없습니다. 짝수와 홀수의 순서에 대한 제약 조건이 존재하기 때문입니다. 따라서 각 순서를 유지하면서, 짝수 시퀀스와 홀수 시퀀스의 맨 앞 원소들을 비교해 더 큰 조합을 만드는 쪽을 선택하는 방식으로 진행해야 합니다.

핵심은 두 숫자 E(짝수)와 O(홀수)를 이어 붙일 때 "EO"와 "OE" 중 어느 조합이 더 큰 수를 만드는지 문자열 비교를 통해 판단하는 것입니다.

알고리즘

1단계 : 짝수용과 홀수용 두 개의 리스트를 생성하여 각각의 순서를 유지합니다.
2단계 : 각 리스트에서 맨 앞 원소를 하나씩 가져와 어느 조합이 더 큰 수를 만드는지 확인합니다.
        예를 들어, 짝수 E와 홀수 O가 각 리스트의 맨 앞에 있다면 EO와 OE 중 더 큰 값을 판별합니다.
3단계 : 더 큰 조합을 최종 결과 시퀀스에 추가합니다.
4단계 : 최종 시퀀스를 출력합니다.

C++ 구현 예제

이제 위 알고리즘을 기반으로 프로그램을 작성해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
string merge(vector<string> arr1, vector<string> arr2) {
    int n1 = arr1.size();
    int n2 = arr2.size();
    int i = 0, j = 0;
    string big = "";
    while (i < n1 && j < n2) {
        if ((arr1[i]+arr2[j]).compare((arr2[j]+arr1[i])) > 0)
            big += arr1[i++];
        else
            big += arr2[j++];
    }
    while (i < n1)
        big += arr1[i++];
    while (j < n2)
        big += arr2[j++] ;
    return big;
}
string largestNumber(vector<string> arr, int n) {
    vector<string> even, odd;
    for (int i=0; i<n; i++) {
        int lastDigit = arr[i].at(arr[i].size() - 1) - '0';
        if (lastDigit % 2 == 0)
            even.push_back(arr[i]);
        else
            odd.push_back(arr[i]);
    }
    string biggest = merge(even, odd);
    return biggest;
}
int main() {
    vector<string> arr;
    arr.push_back("17");
    arr.push_back("80");
    arr.push_back("99");
    arr.push_back("27");
    arr.push_back("14");
    arr.push_back("22");
    int n = arr.size();
    cout<<"배열로 만들 수 있는 가장 큰 수 = "<<largestNumber(arr, n);
    return 0;
}

실행 결과

배열로 만들 수 있는 가장 큰 수 = 801799271422

코드 설명 및 시간 복잡도

largestNumber 함수는 먼저 각 숫자의 마지막 자릿수를 확인하여 짝수와 홀수를 분리합니다. 이때 마지막 자릿수만 검사하면 되므로 숫자 전체를 정수로 변환할 필요가 없습니다.

merge 함수는 병합 정렬의 병합 과정과 유사하게 동작합니다. 두 리스트의 맨 앞 원소를 이어 붙인 문자열(EO vs OE)을 사전식으로 비교하여 더 큰 수를 만드는 쪽을 결과에 추가합니다. 모든 원소가 처리될 때까지 이 과정을 반복하므로, 전체 시간 복잡도는 O(N × M)입니다. 여기서 N은 원소의 개수, M은 숫자의 평균 길이입니다.