C++로 숫자의 가장 작은 순열 구하기

이 문제에서는 매우 큰 수 N이 주어지며, 우리의 목표는 주어진 숫자를 재배열하여 만들 수 있는 가장 작은 순열(가장 작은 수)을 찾는 것입니다.

문제 이해를 위한 예시

입력

N = 4529016

출력

해결 접근 방법

이 문제를 해결하는 가장 간단한 방법은 다음과 같습니다.

먼저, 긴 정수 값을 문자열로 저장합니다. 그다음 문자열을 오름차순으로 정렬하면 기본적인 결과를 얻을 수 있습니다. 하지만 정렬된 결과 앞쪽에 0이 위치하는 경우가 있으므로, 모든 선행 0(leading zeros)을 첫 번째 0이 아닌 숫자 뒤로 이동시켜야 합니다. 예를 들어 '0124569'라면 '1024569'처럼 0이 아닌 가장 작은 숫자를 맨 앞에 배치하고 나머지 0들을 그 뒤에 배치하면 됩니다.

구현 예제

아래 프로그램은 위에서 설명한 해결 방법이 실제로 동작하는 과정을 보여줍니다.

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

string smallestNumPer(string s) {
    int len = s.length();
    // 문자열을 오름차순으로 정렬
    sort(s.begin(), s.end());
    int i = 0;
    // 선행 0의 개수만큼 인덱스 이동
    while (s[i] == '0')
        i++;
    // 맨 앞의 0과 첫 번째 0이 아닌 숫자를 교환
    swap(s[0], s[i]);
    return s;
}

int main() {
    string s = "4529016";
    cout << "주어진 숫자: " << s << endl;
    cout << "가장 작은 순열: " << smallestNumPer(s);
    return 0;
}

실행 결과

주어진 숫자: 4529016
가장 작은 순열: 1024569

동작 원리 정리

이 알고리즘의 시간 복잡도는 정렬 단계가 지배적이므로 O(n log n)입니다. 여기서 n은 숫자의 자릿수입니다. 정렬 후에는 최악의 경우 O(n) 시간이 추가로 소요되어 전체적으로 효율적입니다.

핵심 로직을 요약하면 다음과 같습니다.

1. 숫자를 문자열로 변환 후 오름차순 정렬
2. 정렬 결과에서 선행 0의 개수를 확인
3. 맨 앞 자리와 첫 번째 0이 아닌 숫자를 교환하여 유효한 가장 작은 수 완성