[정렬] 가장 큰 수

yerin6860·2020년 9월 26일
0

프로그래머스

목록 보기
28/30

|| 문제설명 ||

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

    • 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.
  2. 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 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
#include
#include

using namespace std;

bool compare(string a, string b) {
return a + b > b + a;
}

string solution(vector numbers) {
string answer = "";
vector 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;
}

![](https://media.vlpt.us/images/yerin6860/post/21fa6f67-e423-4607-b1b1-dbc7cb396e88/image.png)

> * **예외발견**
  ###### 모든 원소가 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
#include
#include

using namespace std;

bool compare(string a, string b) {
return a + b > b + a;
}

string solution(vector numbers) {
string answer = "";
vector 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;
}


![](https://media.vlpt.us/images/yerin6860/post/d8653322-4895-4c84-b9d4-89106eb85707/image.png)

0개의 댓글