[정렬] 가장 큰 수

yyeahh·2020년 9월 26일

프로그래머스

목록 보기

28/35

|| 문제설명 ||

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.
- 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.
순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성하라.

numbers : 0 또는 양의 정수가 담긴 배열

_ numbers의 길이 : 1 이상 100,000 이하
_ numbers의 원소 개수 : 0 이상 1,000 이하
_ 정답이 너무 클 수 있으니 문자열로 바꾸어 return

|| 문제해결방법 ||

- 각 원소들을 string의 형태로 변환하여 새로운 string타입의 백터변수(n)에 추가
- sort함수를 통해 n을 정렬
	(이때 {"3", "30"}, {"42", "48"} 처럼 자리수가 여러개라면 
    	첫 번째 자리수부터 비교하여 더 큰수를 앞으로 정렬시켜야한다.
    	sort에 사용할 특별한 compare함수 추가)
- 정렬한 원소들을 answer에 합침

|| 코드 ||

[2020.09.26] 실패

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

using namespace std;

bool compare(string a, string b) {
    if(a == b) return compare(*(&a +1),*(&b+1) );
    else return a > b;
}

string solution(vector<int> numbers) {
    string answer = "";
    vector<string> n;
    for(auto i : numbers) {
        n.push_back(to_string(i));
    }
    sort(n.begin(), n.end(), compare);
    for(auto i : n) {
        answer.append(i);
    }
    return answer;
}

bool compare(string a, string b) {
   if(a == b) return compare(*(&a +1),*(&b+1) );
   else return a > b;
}
각 자리수를 비교하기에는 메모리초과와 3, 30으로 인해 생기는 303, 330을 처리하지 못한다.

애초에 a + b 가 b + a보다 크게하면 되지 않을까

[2020.09.26] 실패

- compare함수 수정

#include <string>
#include <vector>
#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> n;
    for(auto i : numbers) {
        n.push_back(to_string(i));
    }
    sort(n.begin(), n.end(), compare);
    for(auto i : n) {
        answer.append(i);
    }
    return answer;
}

예외발견
모든 원소가 0일 경우
{100, 0, 0, 0, 0}처럼 전부 0이 아닌 경우이면 return 1000000이지만 전부 0일 경우 return 0000000처럼 나오므로
answer의 0번째 자리의 숫자가 0인지 아닌지를 판단한다.

[2020.09.26] 성공

- if(answer[0] == '0') return "0"; 추가

#include <string>
#include <vector>
#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> n;
    for(auto i : numbers) {
        n.push_back(to_string(i));
    }
    sort(n.begin(), n.end(), compare);
    for(auto i : n) {
        answer.append(i);
    }
    if(answer[0] == '0') return "0";
    return answer;
}

[2021.01.31]

#include <string>
#include <vector>
#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> tmp;
    
    for(auto i : numbers) {
        tmp.push_back(to_string(i));
    }
    sort(tmp.begin(), tmp.end(), compare);
    for(auto i : tmp) {
        answer += i;
    }
    return (answer[0] == '0') ? "0" : answer;
}