Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 최대 한 번의 자리 교환(swap)으로 만들 수 있는 가장 작은 숫자 구하기

이 문제에서는 하나의 양의 정수가 주어집니다. 우리의 과제는 최대 한 번의 자리 교환(swap) 연산만 사용하여 만들 수 있는 가장 작은 숫자를 구하는 프로그램을 작성하는 것입니다.

즉, 기존 숫자의 자릿수들을 이용해 새로운 숫자를 만들되, 딱 한 쌍의 자릿수만 서로 바꿀 수 있다는 조건이 있습니다.

문제 이해를 위한 예시

입력: n = 63519
출력: 36519

위 예시에서 첫 번째 자리의 '6'과 두 번째 자리의 '3'을 서로 바꾸면 63519 → 36519가 되며, 이것이 한 번의 스왑으로 만들 수 있는 가장 작은 숫자입니다.

해결 방법 1: 모든 경우의 수 탐색 (브루트 포스)

가장 직관적인 방법은 주어진 숫자에서 교환 가능한 모든 자릿수 쌍을 바꿔보면서 생성되는 숫자들을 확인하고, 그중 가장 작은 값을 반환하는 것입니다.

구체적인 절차는 다음과 같습니다.

  • 숫자를 문자열로 변환합니다.
  • 이중 반복문을 통해 가능한 모든 위치 쌍 (i, j)에 대해 두 자릿수를 교환해 봅니다.
  • 교환한 결과가 현재까지의 최솟값보다 작으면 갱신합니다.
  • 다시 원래대로 되돌린 후 다음 쌍을 검사합니다.

구현 예제

#include <iostream>
using namespace std;

int findSmallestNumSwapDig(int N){

    string strNum = to_string(N);
    string temp = strNum;
    for (int i = 0; i < strNum.size(); i++) {
        for (int j = i + 1; j < strNum.size(); j++) {
            swap(strNum[i], strNum[j]);
            if (stoi(strNum) < stoi(temp))
                temp = strNum;
            swap(strNum[i], strNum[j]);
        }
    }
    return stoi(temp);
}
int main(){
    int num = 792156;
    cout<<"원래 숫자: "<<num<<endl;
    cout<<"한 번의 자리 교환으로 만든 가장 작은 숫자: "<<findSmallestNumSwapDig(num) << endl;
    return 0;
}

실행 결과

원래 숫자: 792156
한 번의 자리 교환으로 만든 가장 작은 숫자: 192756

이 방법은 모든 쌍을 검사하므로 시간 복잡도는 O(n²)입니다. 숫자의 길이가 짧다면 충분히 실용적이지만, 더 효율적인 방법도 존재합니다.

해결 방법 2: 보조 배열(aux)을 활용한 최적화

두 번째 방법은 추가 보조 배열 aux[]를 사용하여 불필요한 비교를 줄이는 방식입니다.

aux[i]는 현재 인덱스 i보다 오른쪽(더 큰 인덱스)에 있는 자릿수 중 가장 작은 값의 인덱스를 저장합니다. 만약 그런 자릿수가 없다면 -1로 초기화합니다.

동작 원리는 다음과 같습니다.

  1. 오른쪽에서 왼쪽으로 배열을 순회하면서 aux 배열을 채웁니다.
  2. 인덱스 0부터 탐색하면서, 현재 값보다 작은 숫자가 aux 배열에 있는지 확인합니다. 단, 맨 앞자리와 교환할 때는 결과가 0으로 시작하면 안 되므로 0인 자릿수는 제외합니다.
  3. 조건에 맞는 자릿수를 찾으면 arr[i]와 arr[aux[i]]를 교환하고 결과를 반환합니다.

구현 예제

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

int findSmallestNumSwapDig(int N){

    string num = to_string(N);
    int n = num.size();
    int auxArr[n], right;
    auxArr[n - 1] = -1;
    right = n - 1;
    for (int i = n - 2; i >= 1; i--) {
        if (num[i] >= num[right])
            auxArr[i] = right;
        else {
            if (num[i] == num[i + 1])
                auxArr[i] = right;
            else {
                auxArr[i] = -1;
                right = i;
            }
        }
    }
    int small = -1;
    for (int i = 1; i < n; i++)
    if (num[i] != '0') {
        if (small == -1) {
            if (num[i] < num[0])
                small = i;
        }
        else if (num[i] <= num[small])
            small = i;
    }
    if (small != -1)
        swap(num[0], num[small]);
    else {
        for (int i = 1; i < n; i++) {
            if (auxArr[i] != -1 && num[i] != num[auxArr[i]]) {
                swap(num[i], num[auxArr[i]]);
                break;
            }
        }
    }
    return stoi(num);
}
int main(){
    int num = 792156;
    cout<<"원래 숫자: "<<num<<endl;
    cout<<"한 번의 자리 교환으로 만든 가장 작은 숫자: "<<findSmallestNumSwapDig(num)<< endl;
    return 0;
}

실행 결과

원래 숫자: 792156
한 번의 자리 교환으로 만든 가장 작은 숫자: 192756

정리

두 방법 모두 동일한 결과를 출력하지만, 브루트 포스 방식은 O(n²)의 시간이 걸리는 반면, 보조 배열을 활용한 방식은 선형 시간에 가깝게 문제를 해결할 수 있어 더 큰 입력값에 유리합니다. 특히 맨 앞자리가 0이 되는 경우를 처리하는 로직이 핵심 포인트임을 기억하세요.