C++ 배열 회전으로 숫자를 연결해 만들 수 있는 최댓값 구하기

이번 글에서는 원형 배열(Circular Array)에 담긴 숫자들을 회전시켜 연결함으로써 만들 수 있는 최댓값을 구하는 방법을 다룹니다. 먼저 문제 상황과 해결 전략을 살펴보고, 이어서 실제 동작하는 C++ 코드까지 확인해 보겠습니다.

문제 개요

원형 배열이란 첫 번째 요소가 마지막 요소 바로 다음에 위치한다고 간주되는 배열을 말합니다. 즉, 배열의 끝과 시작이 이어져 있는 형태로, 주로 큐(Queue)를 구현할 때 활용됩니다.

배열의 각 요소는 자릿수가 같거나 서로 다를 수 있습니다. 우리의 목표는 필요하다면 요소들의 순서를 회전시키면서 숫자들을 연결하여 가능한 가장 큰 수를 만드는 것입니다.

핵심 아이디어

모든 요소의 맨 앞자리 숫자(최상위 자릿수)를 비교하여 그중 가장 큰 값을 찾습니다. 맨 앞자리 숫자가 가장 큰 요소가 결과 숫자의 첫 자리에 배치됩니다. 이후 배치는 해당 요소의 위치에 따라 다음과 같이 결정됩니다.

첫 번째 위치에 있다면 → 인덱스 1부터 n-1까지의 요소들을 그대로 뒤에 붙입니다.
중간 인덱스 i에 있다면 → 인덱스 i+1부터 n-1까지의 요소들을 먼저 붙인 뒤, 인덱스 0부터 i-1까지의 요소들을 이어 붙입니다.
마지막 위치에 있다면 → 인덱스 0부터 i-1까지의 요소들을 그 뒤에 붙입니다.

예제 1

입력

Arr[] = { 121, 43, 65, 32 }

출력

최댓값: 653212143

설명: 맨 앞자리 숫자 중 가장 큰 값은 6입니다. 따라서 65를 첫 자리에 놓고, 그 뒤에 32, 121, 43 순으로 이어 붙입니다. Arr[]은 원형 배열이므로 이러한 회전 배치가 가능합니다.

예제 2

입력

Arr[] = { 1101, 9, 321, 77 }

출력

최댓값: 9321771101

설명: 맨 앞자리 숫자가 가장 큰 요소는 9입니다. 9를 첫 자리에 놓고, 그 뒤에 321, 77, 1101 순으로 연결합니다. 역시 원형 배열의 특성 덕분에 가능한 배치입니다.

알고리즘 접근 방식

프로그램의 동작 흐름은 다음과 같습니다.

배열 arr[]에 숫자들이 저장되어 있습니다.
함수 Largest(int arr[], int n)는 배열과 그 길이 n을 입력받아, 연결로 만들 수 있는 최댓값을 출력합니다.
변수 maxx는 맨 앞자리 숫자가 가장 큰 요소를 저장하며, 초기값은 0입니다.
변수 pos는 maxx의 인덱스를 저장합니다.
i = 0부터 n-1까지 반복하면서, 각 arr[i]를 10으로 나누기를 반복해 맨 앞자리 숫자를 찾습니다. 나눗셈 과정에서 나머지는 항상 일의 자리 숫자를 의미하고, 몫이 0이 되는 시점의 나머지가 곧 맨 앞자리 숫자입니다.
현재 찾은 숫자가 지금까지의 최댓값보다 크면(num == 0일 때, 즉 rem이 맨 앞자리 숫자일 때) maxx와 pos를 갱신합니다.
마지막으로 인덱스 pos부터 배열 끝까지의 요소를 출력한 뒤, 인덱스 0부터 pos-1까지의 요소를 이어서 출력합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
void Largest(int arr[], int n){
    int maxx = 0;
    int pos = 0; // 맨 앞자리 숫자가 가장 큰 요소의 인덱스
    for (int i = 0; i < n; i++) {
        int num = arr[i];
        // 마지막(맨 앞) 자릿수 확인
        while (num != 0) {
            int rem = num % 10;
            num = num / 10;
            if (num == 0) {
                if (maxx < rem) {
                    maxx = rem;
                    pos = i;
                }
            }
        }
    }
    // 최댓값 출력
    cout << "연결로 만든 최댓값: ";
    for (int i = pos; i < n; i++)
        cout << arr[i];
    for (int i = 0; i < pos; i++)
        cout << arr[i];
}
int main(){
    int Arr[] = { 12, 34, 56, 98 };
    int size = 4;
    Largest(Arr, size);
    return 0;
}

실행 결과

연결로 만든 최댓값: 98123456

정리

이 알고리즘은 각 숫자를 반복적으로 10으로 나누어 맨 앞자리 숫자를 추출하고, 그중 가장 큰 값을 가진 요소를 기준점으로 삼아 배열을 회전시키는 방식으로 동작합니다. 원형 배열의 특성을 활용하면 별도의 정렬 없이도 O(n) 시간 복잡도로 최댓값 배치를 찾을 수 있다는 점이 이 접근법의 장점입니다.