💻 가장 큰 수

분류 : Sort (정렬)

사용 언어 : C++

문제 링크

🤔 문제 이해

문제 설명

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

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

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

​

제한 사항

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

해결 방안

이 문제는 배열을 자르는 코드, 정렬하는 코드, 랜덤 액세스를 할 수 있어야 한다.

💡 문제 풀이

방법 1 )

priority_queue를 사용하여 최적의 값을 추출한다.

#include <string>
#include <vector>
#include <queue>

using namespace std;

struct cmp {
    bool operator()(string a, string b) {
        // 두 문자열을 더했을 때 더 큰 값이 나오는 순으로 내림차순
        return a + b < b + a;
    }
};

string solution(vector<int> numbers) {
    string answer = "";

    priority_queue<string, vector<string>, cmp> sorting;

    for (int i = 0; i < numbers.size(); i++) {
        // 숫자를 문자열로 바꿔 push_back
        sorting.push(to_string(numbers[i]));
    }

    while (sorting.size()) {
        // 정렬된 문자열을 answer에 추가한다.
        answer = answer + sorting.top();
        sorting.pop();
    }

    while (answer[0] == '0' && answer.length() > 1) answer = answer.substr(1);	
    // 만약 문자열 맨 앞에 0이 올 시 제거해준다.
    // "00000" 일 시 "0"만 남을 수 있도록 길이가 1 초과일때만 하도록 조건 추가

    return answer;
}

/*
정확성  테스트
    테스트 1 〉	통과 (460.64ms, 9.94MB)
    테스트 2 〉	통과 (150.97ms, 6.79MB)
    테스트 3 〉	통과 (758.51ms, 11.2MB)
    테스트 4 〉	통과 (2.30ms, 3.95MB)
    테스트 5 〉	통과 (361.40ms, 8.61MB)
    테스트 6 〉	통과 (279.82ms, 8.07MB)
    테스트 7 〉	통과 (0.04ms, 3.93MB)
    테스트 8 〉	통과 (0.02ms, 3.93MB)
    테스트 9 〉	통과 (0.02ms, 3.84MB)
    테스트 10 〉	통과 (0.02ms, 3.94MB)
    테스트 11 〉	통과 (0.03ms, 3.95MB)
    
채점 결과
    정확성: 100.0
    합계: 100.0 / 100.0
*/

시간 복잡도 : 2n + n * log n

숫자를 문자열로 변환하여 priority_queue에 넣어주고 top()을 answer에 추가한다.
만약 문자열의 맨 앞에 0이 올 시, 앞의 0을 모두 제거

방법 2 )

Algorithm의 Sort를 통하여 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) {
    string answer = "";

    vector<string> sorting;	// 문자열 정렬용 vector

    for (int i = 0; i < numbers.size(); i++) {
        // 숫자를 문자열로 바꿔 push_back
        sorting.push_back(to_string(numbers[i]));
    }

    // cmp조건으로 문자열 vector를 sorting
    sort(sorting.begin(), sorting.end(), cmp);

    for (int i = 0; i < sorting.size(); i++) {
        // 정렬된 문자열을 answer에 추가한다.
        answer = answer + sorting[i];
    }

    while (answer[0] == '0' && answer.length() > 1) answer = answer.substr(1);	
    // 만약 문자열 맨 앞에 0이 올 시 제거해준다.
    // "00000" 일 시 "0"만 남을 수 있도록 길이가 1 초과일때만 하도록 조건 추가

    return answer;
}

/*
정확성  테스트
    테스트 1 〉	통과 (420.93ms, 10MB)
    테스트 2 〉	통과 (138.03ms, 6.84MB)
    테스트 3 〉	통과 (727.45ms, 11.3MB)
    테스트 4 〉	통과 (2.06ms, 4MB)
    테스트 5 〉	통과 (333.98ms, 8.79MB)
    테스트 6 〉	통과 (259.32ms, 8.11MB)
    테스트 7 〉	통과 (0.03ms, 3.95MB)
    테스트 8 〉	통과 (0.02ms, 3.96MB)
    테스트 9 〉	통과 (0.03ms, 3.91MB)
    테스트 10 〉	통과 (0.02ms, 3.94MB)
    테스트 11 〉	통과 (0.04ms, 3.96MB)
    
채점 결과
    정확성: 100.0
    합계: 100.0 / 100.0
*/

시간 복잡도 : 2n + n * log n

숫자를 문자열로 변환하여 vector에 넣어주고 sort하여 answer에 추가한다.
만약 문자열의 맨 앞에 0이 올 시, 앞의 0을 모두 제거