[c++] 프로그래머스 :: 가장 큰 수 (문제 풀이, 코드)

가장 큰 수

문제

문제 설명

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

제한 사항

• numbers의 길이는 1 이상 100,000 이하입니다.
• numbers의 원소는 0 이상 1,000 이하입니다.
• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

입출력 예

numbers	return
[6, 10, 2]	6210
[3, 30, 34, 5, 9]	9534330

 

---

코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

void swap(vector<int>& arr, int idx1, int idx2) {
    int tmp = arr[idx1];
    arr[idx1] = arr[idx2];
    arr[idx2] = tmp;
}

bool compareModule(int a, int b){
    int num1 = stoi(to_string(a).append(to_string(b)));
    int num2 = stoi(to_string(b).append(to_string(a)));

    if(num1>num2)
        return true; // 현재 순서가 맞음
    else
        return false; // 현재 순서가 틀림

}

void quickSortModule(vector<int>& arr, int left, int right) {
    // quickSort로 시간복잡도 줄이기
    if (right - left <= 1)
        return;

    int pivot = arr[left];
    int high = left+1;
    int low = right-1;
    while (1) { // n => 10^5
        while(high<right){
            if (compareModule(pivot, arr[high])) //10^3
                break;
            else
                high++;
        }
        while(low>left){
            if (compareModule(arr[low], pivot))
                break;
            else
                low--;
        }
        if (high >= low)
            break;
        swap(arr, high, low);
    }
    swap(arr, left, low);
    quickSortModule(arr, left, low);
    quickSortModule(arr, low + 1, right);
}

string solution(vector<int> numbers) {
    string answer = "";

    quickSortModule(numbers, 0, numbers.size()); //nlgn

    int flag = 0; // 앞의 0 지워주기
    for(int i=0; i<numbers.size(); i++){
        if(flag==0 && numbers[i]==0)
            continue;
        else
            flag=1;
        answer+=to_string(numbers[i]);
    }
    if(answer=="") // 답이 0일 경우
        answer="0";

    return answer;
}

 

풀이

 주어진 배열을 퀵 정렬로 정렬하되, 비교를 단순히 수의 대소로 하지 않고 따로 비교 모듈을 만들어 사용했다. 비교 모듈은 두 수를 이어붙였을 때, 더 큰 수가 나오도록 두 수의 현재 상대적 위치가 바른 지를 반환해준다.

 예를 들어 3과 30이 있을 때, 그대로 이어붙이면 330이고 30을 앞으로 해서 이어붙이면 303이다. 330>303 이므로 현재 위치가 올바르다. 따라서 true 반환하는 식이다.

 

 quickSort를 사용한 이유는 처음에 삽입 정렬로 구현하였다가 n^2의 시간복잡도를 가지는 것을 깨닫고 n이 10^5이기 때문에 시간초과가 뜰 수 있겠다고 판단하였기 때문이다.

void insertionSort(vector<int>& arr){
    // 삽입 정렬
    for(int i=1; i<arr.size(); i++){
        int pos=i;
        while(pos>0){
            if(compareModule(arr[pos-1],arr[i]))
                break;
            --pos;
        }
        int tmp = arr[i];
        arr.erase(arr.begin()+i); // 기존 요소 지우기
        arr.insert(arr.begin()+pos, tmp); // 적절한 위치에 끼워넣기
    }
}

 

 중간에 두 수를 이어붙이는 과정을 어렵게 해석해서 두 수의 자릿수를 맞춰준 수 작은 수에 큰 수의 앞자리를 붙이는 식으로 해서 비교해보기도 하고,

bool compareModule(int a, int b){
    if(a<b)
        return !compareModule(b,a);

    int sub = returnLength(a)-returnLength(b); // 자릿수 차이
    for(int i=0; i<sub; i++){
        b*=10;
    }
    b+=((int)(a/pow(10,returnLength(a)-sub))); // b의 앞자리 뒤에 붙여주기

    if(a<=b)
        return false;
    else
        return true;
}

 

ex_) 4, 495 => 400 + 49(495의 앞자리) , 495 => 449 , 495 비교

 

 두 수를 그냥 이어붙이는데 문자열을 사용한 것이 아니라 위와 동일한 방법으로 비교해보기도 하고,

bool compareModule(int a, int b){
    int a_len = returnLength(a);
    int b_len = returnLength(b);

    int num1 = (a*pow(10,b_len))+b;
    int num2 = (b*pow(10,a_len))+a;

    if(num1>num2)
        return true; // 현재 순서가 맞음
    else
        return false; // 현재 순서가 틀림

}

ex_) 4, 495 => 4000 + 495, 4950 + 4

 

결국 to_string (int => string) 과 stoi (string => int)라는 함수를 써서 해결했다.

채점 결과

 

다른 사람의 풀이

bool compare(const string &a, const string &b)
{
    if (b + a < a + b)
        return true;
    return false;
}

string solution(vector<int> numbers) {
    string answer = "";

    vector<string> strings;

    for (int i : numbers)
        strings.push_back(to_string(i));

    sort(strings.begin(), strings.end(), compare);

    for (auto iter = strings.begin(); iter < strings.end(); ++iter)
        answer += *iter;

    if (answer[0] == '0')
        answer = "0";

    return answer;
}

숏코딩 만세...!

• sort는 비교 함수를 줘서 구현할 수 있다.
• compare 함수는 자동 형변환을 이용해서 저렇게 간단하게 구현할 수 있다.
• 0처리도 쉽게 할 수 있다 => 앞자리가 0이면 뒷자리들은 모두 0이라고 볼 수 있음