문제 내용

문제 설명

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”

문제 분석

1차 시도 : 그냥 1의 자리 숫자가 큰거대로 정렬하면 되지않음? ⇒ 안됨

2차 시도 : 그럼 1의자리 먼저 판단하고 같으면 수가 큰걸 먼저 오게 하면 되는거 아님? ⇒ 안됨

3차 시도 : 그럼 그냥 일일히 숫자 ⇒ 문자열 ⇒ 두개 합쳐서 비교 해봐야지 근데 어떻게하지 하다가 sort에 매개변수로 함수 넣을수 있는거 떠올리고 유레카 외침

작성한 코드

 #include <bits/stdc++.h>
 
using namespace std;
 
bool cmp(int a, int b){
    string temp1 = "";
    string temp2 = "";
    temp1 = to_string(a) + to_string(b);
    temp2 = to_string(b) + to_string(a);
    
    return stoi(temp1) > stoi(temp2);
}
 
string solution(vector<int> numbers) {
    string answer = "";
    sort(numbers.begin(), numbers.end(), cmp);
    
    for(auto& i : numbers){
        if(answer == "0" && i == 0) continue;
        answer += to_string(i);
    }
        
    return answer;
}

우수 코드 분석

#include <algorithm>
#include <string>
#include <vector>
 
using namespace std;
 
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;
}

여긴 그냥 정렬을 string 한 채로 돌려버리심. 저거도 되는구나?

개발기록장

탐색기

가장 큰 수