[Programmers] 가장 큰 수

👀 문제 설명

문제

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"

 

✍🏻풀이

int형 벡터의 numbers를 string형 벡터로 변환해준 후, sort를 사용해 내림차순으로 정렬한다.

그리고 앞에서부터 쭉 이으면 된다고 생각했다.

그런데 두번째 예제같은 경우,

9 5 34 30 3 으로 정렬이 되는데

가장 뒤의 두 숫자를 보면, 303보다 330이 더 크다. 이 경우를 위해 앞에서부터 현재값과 다음값을 비교했다.

a b가 있을 때, a+b가 큰지 b+a가 큰지 비교를 하고, b+a가 클 경우 a와 b의 자리를 바꿔주면 된다고 생각했다.

그런데 이렇게 했을 경우, 입출력 예의 테스트 케이스는 맞지만, 채점 후 제출을 하니 틀린 케이스가 너무 많았다,,ㅠ

찾아보니, sort함수의 세번째 인자인 비교 함수를 사용하면 훨씬 쉽게 문제를 풀 수 있었다!

 

내 코드(틀림)

#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

/**
 int형 벡터를 string으로 바꿔서 내림차순 정렬 후,
 앞에서부터 붙인다
 */
string solution(vector<int> numbers) {
    string answer = "";

    vector<string> stringVector;
    for (int i = 0; i < numbers.size(); i++) {
        string s = to_string(numbers.at(i));

        stringVector.push_back(s);
    }

    // sort
    sort(stringVector.begin(), stringVector.end(), greater<string>()); // 내림차순 정렬 : greater 사용
    for (int i = 0; i < stringVector.size(); i++) {
        /**
         문제)
         2 10 1 로 정렬될 경우,
         2101보다 2110이 더 크다. -> 어떻게 비교?
         */
        if (i != stringVector.size() - 1) {
            string curStr = stringVector.at(i);
            string nextStr = stringVector.at(i + 1);

            if (curStr.at(0) == nextStr.at(0)) {
                int a = stoi(curStr + nextStr);
                int b = stoi(nextStr + curStr);

                if (a < b) {
                    // 현재와 뒤의 값을 바꿔준다.
                    stringVector.at(i) = nextStr;
                    stringVector.at(i + 1) = curStr;
                }
            }
        }

        string cur = stringVector.at(i);
        answer += cur;
    }

    return answer;
}

int main() {
    vector<int> numbers1 = { 6, 10, 2 };
    vector<int> numbers2 = { 3, 30, 34, 5, 9 };

    cout << solution(numbers1) << endl;
    cout << solution(numbers2) << endl;

    return 0;
}

 

sort함수의 세 번째 인자 사용(비교 함수)

//
//  Programmers_42746.cpp
//  Algorithm
//
//  Created by 조수민 on 2020/10/23.
//  Copyright © 2020 조수민. All rights reserved.
//
//  가장 큰 수(https://programmers.co.kr/learn/courses/30/lessons/42746)

#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

/**
 cmp 함수를 만들어 정렬해준다!!
 이 때 비교는 string 형으로 한다.
 */
bool cmp(const string &a, const string &b) {
    return a + b > b + a;
}

string solution(vector<int> numbers) {
    string answer = "";
    
    // int형 벡터 numbers를 string형으로 바꿔 넣는다.
    vector<string> stringVector;
    for (int i = 0; i < numbers.size(); i++) {
        string s = to_string(numbers.at(i));
        
        stringVector.push_back(s);
    }
    
    /**
     sort 함수를 사용한다.
     이때, 마지막 인자에 비교 함수를 넣으면 그 함수 기준으로 정렬을 수행한다!!
     */
    sort(stringVector.begin(), stringVector.end(), cmp);
    
    for (int i = 0; i < stringVector.size(); i++) {
        string cur = stringVector.at(i);
        answer += cur;
    }
    
    if (answer[0] == '0') return "0"; // answer[0]이 0이면 가장 큰 수가 0이라는 뜻이므로 0을 리턴한다.
    
    return answer;
}

int main() {
    vector<int> numbers1 = { 6, 10, 2 };
    vector<int> numbers2 = { 3, 30, 34, 5, 9 };
    
    cout << solution(numbers1) << endl;
    cout << solution(numbers2) << endl;
    
    return 0;
}

[참고] devje8.tistory.com/9