[프로그래머스 - level2] [정렬] 가장 큰 수

코딩테스트 및 개인공부/문제풀이

[프로그래머스 - level2] [정렬] 가장 큰 수

JJPearl 2021. 11. 2. 23:09

문제 설명

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"

풀이 과정

<첫 번째 풀이>

순열이 필요하니까 next_permutation() 함수를 사용하면 되겠다. 이 함수는 정렬되어 있어야 사용 가능.

*순열: 순서가 중요. 순서가 다르면 다른 것으로 본다. / 조합: 순서 상관 없이 뽑음

-질문하기에서 찾아본 반례

[ 979, 97, 978, 81,818,817] , 9799797881881817

[0, 0, 0, 0] , 0 // 11번 오답은 이 테스트케이스 때문

[67,676,677], 67767676

[10, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 987654321101000 // 이 반례에서 시간초과

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

string solution(vector<int> numbers) {
    sort(numbers.begin(),numbers.end());
    vector<string> permutations;
    string answer = "";
    do {
        string temp = "";
        for(auto i = numbers.begin(); i != numbers.end(); ++i) {
            if(i == numbers.begin() && *i == 0) {
                temp = '0';
                break;
            }
            temp += to_string(*i);
        }
        //cout << temp << endl;
        permutations.emplace_back(temp);
        temp = "";
    }while(next_permutation(numbers.begin(),numbers.end()));
    
    sort(permutations.begin(),permutations.end());
    answer = permutations.back();

    return answer;
}

-> 테스트 케이스는 다 통과하지만 채점 시 시간 초과가 뜬다. 내가 작성한 코드가 O(N!) 성능이기 때문에 그런듯.
내가 만든 코드는 모든 경우의 수를 구한 다음 그것을 정렬하여 가장 큰 수를 구하는 것인데 기하급수적으로 처리해야할 경우의 수가 늘어나면 시간초과가 되는 것으로 유추.

애초에 permutation 쓰면 안되고 소팅을 스스로 만들어야 한다고 한다.

-> 애초에 numbers 벡터를 string으로 한뒤 내림차순 소팅한 다음 소팅된 순서로 조합하면 어떨까?

*고려해줘야 하는 부분 : 내림차순 정렬시 예외

-> 3과 30을 비교 했을 때 3이 더 크다고 인식되서 앞쪽에 와야 더 큰 수를 만들 수 있으므로 repeating한 수인 33과 30을 비교해 정렬해 준다.

-> 두자리 수 이상일 때는 첫번째 숫자를 더해줘서 판단할 수 있도록

=> 따라서 사용자 함수로 정렬 필요

-> 여기까지 생각했는데 사용자 함수 compare를 잘못 구현한건지 계속 제대로 정렬이 안되었다.. 그래서 아예 정렬 함수를 직접 구현해야 되나 싶어서 뻘짓을 엄청 오래했다...

-> 질문하기에서 정렬을 위해 비교할 때의 아이디어와 11번 반례의 핵심이 될만한 테스트 케이스를 발견했다

Case 1.
[383, 38] => "38383"
[838, 83] => "83883"
Case 2.
[0, 0, 0] => 0

=> compare함수에서 내림차순 정렬을 위해 두 string을 비교하는 기준을 str1과 str2를 더한 것으로 정하면 되겠다는 아이디어가 떠올랐다!

코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

bool compare(const string& s1, const string& s2) {
    if(s1+s2 > s2+s1) {
        return true;
    }
    else
        return false;
}

string solution(vector<int> numbers) {
    vector<string> strVec;
    string answer = "";
    for(auto i = numbers.begin(); i != numbers.end(); ++i) {
        strVec.emplace_back(to_string(*i));
    }
    
    sort(strVec.begin(),strVec.end(),compare);
    
     for(auto i = strVec.begin(); i != strVec.end(); ++i) {
        //cout << *i << ',';
        if(i == strVec.begin() && *i == "0")
        {
            answer = *i;
            break;
        }
        answer += *i;
    }

    return answer;
}

필요 지식

- algorithm 헤더의 sort함수를 사용자 정의 함수 기준으로 정렬하는 법

https://leeeegun.tistory.com/5

[C++ STL] Sort() 사용법 및 compare 함수

sort 함수는 C++ STL에서 제공하는 함수로써 정렬에 이용되며 헤더를 include 하여 사용 할 수 있다. 각종 알고리즘 문제에서도 간단하게 사용 할 수 있어서 자주 쓰이는데, 이 함수의 시간 복잡도는 n

leeeegun.tistory.com

알게된 것

- vector는 front(),back() 사용

- sort할 때 greater는 내림차순, less는 오름차순 헷갈리지 말기

- sort(vec.begin(), v.end()) : 오름차순(default)

- sort(vec.begin(), v.end(), less<type>()) : 오름차순

- sort(vec.begin(), v.end(), greater<type>()) : 내림차순