[Programmers / Sorting] - 가장 큰 수 C++ 풀이

---

 

프로그래머스 - 코딩 테스트 고득점 키트

https://programmers.co.kr/learn/courses/30/lessons/42746

 

문제

 

 

 

풀이

 

이 문제를 풀이하는 방법은, 무조건 주어진 숫자의 첫번째 자리수가 가장 큰 것을 먼저 둬야한다는것이다.
그리고 자리수가 같을 경우에는 어떻게 합쳤을때가 더 큰지를 비교해야하는데, 이는 각 숫자를 문자열화 시키면 쉽게 풀이가 가능하다.

먼저 to_string 함수를 통해서 입력된 숫자값들을 문자열로 전환해준뒤, str_numbers라는 string 벡터에 push한다.

string에서 +연산은 문자열을 합치는 연산이므로 a+b와 b+a를 비교했을때 어떤 것이 더 큰지를 비교하는 compare함수를 만들어준뒤, sort함수를 사용한다. 

 

그 후 정렬된 순서대로 앞에서부터 쓰면 정답을 얻을 수 있다.

 

 

코드

 

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

using namespace std;

bool compare(string a, string b)
{
    return a+b > b+a;
}

string solution(vector<int> numbers) {
    string answer = "";
    vector<string> str_numbers;
    for(auto number : numbers)
        str_numbers.push_back(to_string(number));     
    sort(str_numbers.begin(),str_numbers.end(),compare);
    if(str_numbers[0] == "0")
        return "0";
    for(auto number : str_numbers)
        answer += number;
    return answer;
}

 

 

평가

 

compare함수를 통해 문자열 a+b, b+a의 값을 내림차순으로 정렬하여 풀 수 있다는 것을 알아둬야하는 문제이다.

STL의 sort함수와 compare의 활용법을 알아두면 풀이가 가능하다.

 

해당 문제를 int형 숫자를 써서 풀려고하면 다소 복잡해지므로 to_string함수를 사용하는 방법에 대해서 잘 알아두고 넘어가자.