[프로그래머스 Level 2] [정렬] 가장 큰 수 (C++)

이번엔 굉장히 빡센 친구를 들고 왔습니다. ~~이게 왜 Level2야...~~

개인적으로 이 문제는 어렵게 생각하면 끝도없이 어려워지는 문제라고 생각합니다.

제가 그랬거든요....

출처 : 프로그래머스 코딩테스트 연습 고득점KIT, programmers.co.kr/learn/courses/30/lessons/42746

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

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰

programmers.co.kr

0. 문제 설명

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

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

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

0.0. 제한 사항

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

0.1. 입출력 예

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

1. 풀이 과정

풀이과정 자체는 크게 어렵지 않습니다. (정렬을 생각해내는게 어려운거지...)

제가 필기를 했을 때랑은 순서를 조금 뒤바꿨는데, 문제에서 원하는 정렬은 int형태로는 불가능해보였기 때문입니다.

먼저 int형태의 아이템들을 vector<string>에 string형태로 바꿔서 넣어줍니다. to_string()함수를 사용하면 int형 자료를 string형으로 바꿀 수 있습니다.

그리고 정렬합니다. 정렬 방식은 앞에 있는 자리수가 크면 앞으로 옵니다. 다만 같은 경우, 다음 자리수를 비교합니다. 여기서 다음 자리수가 첫째 자리수보다 작은 경우 그 수는 첫째 자리수 하나만 존재하는 수보다 뒤에 위치하게 됩니다. 그 외의 경우에는 동일하게 자리수가 크면 앞으로 오게 됩니다. 만약 또 같다면, 다음 자리로 넘어가서 다시 비교합니다. 이번에도 자리수가 큰 쪽이 앞으로 오게 되고, 만약 첫째 자리보다 작다면 이번에도 첫째 자리수 하나만 존재하는 수보다 뒤에 위치합니다. 이 방법으로 하면 1000의 경우도 예외사항으로 처리해줘야겠죠. 이것들을 모두 코드로 구현하고 오류사항도 다 잡아낸다는 것은 굉장히 어려운 일입니다.

그래서 다른 방법을 떠올려보면, 미리 합친 것을 비교하는 것입니다. return에 들어가는 것은 numbers 조합들 중에 가장 큰 수입니다. 가장 큰 수를 고르는 방법은 굳이 정렬 방식을 만들 필요가 없이 일반적인 10진수의 큰 수 구하기와 동일합니다. 그렇기 때문에 조합하고 비교하면 보다 편하게 정렬할 수 있습니다.

앞+뒤, 그리고 뒤+앞 했을 때 큰 수가 앞에 오도록 만들기 위해 cmp라는 함수를 하나 만들어서 리턴값을 받아줍니다. 그리고 나서는 아래 적은 그대로 하시면 됩니다. 정렬해주고, answer에 순서대로 넣어주면 끝입니다.

다만 한 가지 해야할 점은 numbers의 원소에 0이 들어갈 수 있습니다. 만약 모든 원소가 0이라면, 00000000이 아닌 0이 출력되도록 하기 위해서 예외처리를 해 줘야 합니다. 이 부분만 처리하면 끝이 납니다. (생각보다 코드는 짧습니다!)

2. 소스 코드

#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) {
    string answer = "";
    vector<string> numb;
    string chk = "";
    for(int i = 0; i < numbers.size(); ++i)
        numb.push_back(to_string(numbers[i]));
    sort(numb.begin(), numb.end(), cmp);
    for (int i = 0; i < numb.size(); ++i)
        answer += numb[i];
    for (int i = 0; i < numb.size(); ++i)
        chk += "0";
    if (chk == answer)
        answer = "0";
         
    return answer;
}

cmp의 파라미터로 왜 call by reference값을 받아준 이유는 제출시간을 단축하기 위함입니다. 아무것도 안쓴다면 call by value로 처리되어 복사과정에 시간이 소요되는데, &를 붙이면 그 과정이 없어집니다. 어짜피 a와 b 값에 영향을 주는 행동은 하지 않았기 때문에 &를 붙이든 떼든 아무 영향이 없습니다. 따라서 시간 단축을 위해서는 붙이는 것이 좋습니다.