프로그래머스 가장 큰 수 c++ (정렬)

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/42746

코딩테스트 연습 - 가장 큰 수

 

문제 설명

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

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

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

제한 사항

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

입출력 예

 

풀이

'프로그래머스 / 정렬 / 가장 큰 수'로 분류되어 있는 문제이다.

 

3, 30의 숫자를 이어서 붙일 수 있는 큰 수는

330, 303 즉 a를 b 앞에 붙이거나, a를 b 뒤에 붙이는 경우를 비교하면 된다.

a와 b를 붙이는 것은, string형식으로 바꿔주면 a+b 혹은 b+a로 쉽게 구현할 수 있다.

 

[3, 30, 34, 5, 9]인 vector가 주어질 때, 가장 큰 수를 이어서 만들려면,

위에서 말한 조건을 기준으로 정렬하면 된다.

 

algorithm헤더의 sort함수는 디폴트가 오름차순으로 즉 a < b 조건으로 정렬되기 때문에,

정렬 조건을 커스텀해서 a+b > b+a로 만들어준다.

 

 

 

코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

bool cmp(string a, string b){

        return a+b>b+a;
}

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