[프로그래머스][정렬][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"

 

---

문제 풀이

접근 방식

이 문제는 주어진 숫자들을 어떤 순서로 정렬해야 가장 큰 수를 만들 수 있는지를 찾는 문제였다.

답을 찾을 수 있는 방법이 많아서 여러 시도를 많이 해본 문제였다.

 

첫 번째로 시도한 방법은 순열을 통해 가장 최댓값을 찾는 방법이었다.

next_permutation으로 모든 가능 경우를 찾아서 구하였는데, 시간 초과로 실패하였다..

 

두 번째로 시도한 방법은 숫자를 변형하여 내림차순으로 정렬하는 방법이었다.

숫자들의 자릿수가 다 다르기 때문에 모두 같은 자릿수로 바꿔주고,

비교 함수를 만들어서 여러 조건을 고려하여 내림차순으로 정렬하고,

그 인덱스에 따라 원래 수를 조합하여 답을 구하였다.

이 방식으로 문제를 해결할 수는 있었으나, 고려해야 할 조건이 많아서 코드가 굉장히 복잡하였다..

좋은 방식은 아닌 거 같아서 더 자세히는 설명하지 않고 코드로 대체하고자 한다..

vector<int> copy_num;

bool cmp(const pair<string, int>& a, const pair<string, int>& b){
    if(a.first == b.first){
        string ab = to_string(copy_num[a.second]) + to_string(copy_num[b.second]);
        string ba = to_string(copy_num[b.second]) + to_string(copy_num[a.second]);
        return ab > ba;
    }
    return a.first > b.first;    
}
 
string solution(vector<int> numbers) {
    // 최대값의 자리수(count) 구하기
    int count = 0;
    int max_num = *max_element(numbers.begin(),numbers.end());
    if(max_num == 0)
        return "0";
    while(max_num > 0){
        max_num /= 10;
        count++;
    }
    
    // 모든 숫자 자리수 맞춰주기(맨 앞의 숫자로 채우기)
    int len = numbers.size();
    vector<pair<string,int>> ans;
    for(int i = 0; i < len; i++) {
        ans.push_back(make_pair(to_string(numbers[i]),i));
        int size = ans[i].first.size();
        for(int j = size; j < count; j++)
            ans[i].first += ans[i].first[0];
    }
    
    // 정렬 후 원래 배열을 answer에 더해주기
    copy_num = numbers;
    sort(ans.begin(), ans.end(), cmp);
    string answer = "";
    for(int i = 0; i < len; i++)
        answer += to_string(numbers[ans[i].second]);
    return answer;
}

 

위의 방법보다 더 좋은 방법이 있지 않을까 찾아보고 고민하다 훨씬 간단하고 쉬운 방법을 알게 되었다.

이 방법은 숫자들을 문자열로 바꿔주고, 두 문자열을 합쳤을 때 더 큰 값이 되는 순서대로 정렬하는 방법이다.

이를 위해서 비교 함수를 아래와 같이 구현해주어야 한다.

이 방법으로 문제를 해결하면 아주 쉽고 간단하게 코드를 작성할 수 있다.

또한, 이 방법이 위의 방법보다 2배 정도 빠르다.

 

bool cmp(const string& a, const string& b){
    return a+b > b+a;
}

 

이 문제를 풀 때 주의해야 하는 경우는 0만 존재하는 경우이다.이 경우에는 00..0이 아닌 0을 리턴해주도록 설정해주어야 모든 테스트 케이스를 통과할 수 있다.

 

---

풀이 코드 - C++

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

using namespace std;

bool cmp(const string& a, const string& b){
    return a+b > b+a;
}

string solution(vector<int> numbers) {
    vector<string> number;
    int size = numbers.size();
    int zero_count = 0;
    for(int i : numbers){
        number.push_back(to_string(i));
        if(i == 0)
            zero_count++;
    }
    if(size == zero_count)
        return "0";
    sort(number.begin(), number.end(),cmp);
    string answer = "";
    for(string i : number){
        answer += i;
    }
    return answer;
}

실행 결과

실행 결과 : 100.0점