[C++][Programmers][정렬] 가장 큰 수

코딩테스트 연습 고득점 Kit 정렬 파트 2번 - 가장 큰 수

 

[문제]

https://school.programmers.co.kr/learn/courses/30/lessons/42746

프로그래머스

 

[해결법]

문제를 보고 든 생각...

"조합함수로 숫자조합은 뽑을 수 있을거 같은데 숫자를 어떻게 합치지?" 였는데

return 이 string  인거 보고 걍 문자열로 합치면 되는구나~를 알았다.

 

(오답)

1) 조합 돌리게 오름차순 정렬해놓기

2) 조합으로 숫자조합 뽑기 -----------------------> 시간초과

3) 반복문 돌리면서 하나로 합쳐서 int로 강제 형번환

4) answer 벡터에 추가

5) 정렬해서 마지막 원소 뽑기

 

(정답)

문자열 비교해서 처음부터 큰 조합으로 정렬하기.

 

참고로 테스트 케이스 11번이 [0,0,0,0] 이라서 그냥 0을 리턴하면 안된다!

 

[알아둘 것]

1. 조합코드

do{
   //조합으로 할 일
}while(next_permutation(v.begin(), v.end()));

next_permutation 의 시간복잡도는 O(N) 이어서 숫자가 크면 부적합하다.

 

2. int to string 코드

to_string(100);

 

3. 문자열도 비교가 된다는 것. 3번째 인자에 bool 함수명 넣기.

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

sort(stringNumbers.begin(), stringNumbers.end(), compare);

 

[코드]

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

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

string solution(vector<int> numbers) {
    string answer;
    vector<string> stringNumbers;
    
    //문자열 비교를 위해 숫자 벡터 -> 문자열 벡터에 넣어두기
    for(int i = 0; i<numbers.size(); i++){
        stringNumbers.push_back(to_string(numbers[i]));
    }
    
    //비교하며 큰 순서대로 정렬
    sort(stringNumbers.begin(), stringNumbers.end(), compare);
    
    //숫자 합치기
    for(int i = 0; i < stringNumbers.size(); i++){
        answer += stringNumbers[i];
    }
    
    //값이 0으로 이루어진 배일이면 0을 리턴하기
    if(answer[0] == '0') return "0";      
    return answer;
}

 

2년전 열심히 할 땐 이렇게 풀었었네 ~

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

bool compare(int a, int b) {
	string string_ab = to_string(a) + to_string(b);
	string string_ba = to_string(b) + to_string(a);
	return string_ab > string_ba;
}

string solution(vector<int> numbers) {
	string answer = "";
	sort(numbers.begin(), numbers.end(), compare);
	for (auto& i : numbers) {
		answer += to_string(i);
	}
	return (answer[0] == '0') ? "0" : answer;
}