[프로그래머스][#42746] 가장 큰수

• [ Question ]

[ Problem ] #42746 가장큰수

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

programmers.co.kr

• Version 1 ( 정렬기준을 정확히 설계해놓지 않았을 경우, 볼 필요 X )

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

using namespace std;

string solution(vector<int> numbers) {
    string answer = "";
    vector<int> Highest_digit;
    vector<int> priority;
    int tmpDigit,tmpNum;
    string str;
    for(int i = 0 ; i < numbers.size(); i++)
    {
        if(numbers[i] / 1000 != 0)
            Highest_digit.push_back(numbers[i] / 1000);
        else if(numbers[i] / 100 != 0)
            Highest_digit.push_back(numbers[i] / 100);
        else if(numbers[i] / 10 != 0)
            Highest_digit.push_back(numbers[i] / 10);
        else
            Highest_digit.push_back(numbers[i]);  
    }
    for(int i = 0 ; i < Highest_digit.size()-1; i++)
    {
        for(int j = 0 ; j < Highest_digit.size()-1 ; j++)
        {
            if(Highest_digit[j] < Highest_digit[j+1])
            {
                tmpDigit = Highest_digit[j];
                Highest_digit[j] = Highest_digit[j+1];
                Highest_digit[j+1] = tmpDigit;
                tmpNum = numbers[j];
                numbers[j] = numbers[j+1];
                numbers[j+1] = tmpNum;
            }
            else if( Highest_digit[j] == Highest_digit[j+1])
            {
                if(numbers[j] < numbers[j+1] && (numbers[j] / 1000 + numbers[j] / 100 % 10 + numbers[j] / 10 % 10 + numbers[j] % 10)  != (numbers[j+1] / 1000 + numbers[j+1] / 100 % 10 + numbers[j+1] / 10 % 10 + numbers[j+1] % 10) )
                {
                    tmpNum = numbers[j];
                    numbers[j] = numbers[j+1];
                    numbers[j+1] = tmpNum;
                }
            }
        }
    }
    for(int i = 0 ; i < numbers.size(); i++)
    {
        str = to_string(numbers[i]);
        answer += str;
    }
    return answer;
}

• 반성하고 다시 짠 코드 ( 정렬 기준을 무엇으로 !! ) 

#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(int i = 0 ; i < numbers.size(); i++)
        tmp.push_back(to_string(numbers[i]));	// to_string()으로 숫자->문자열로
    sort(tmp.begin(),tmp.end(),compare);	// 정렬한다 ( 따로 정의한 compare()함수 기준으로 )
    for(auto i : tmp)	
        answer += i;	// 정답 문자열 변수에 정렬된 문자열벡터요소하나씩 붙이기
    if(answer[0] == '0')	// 모든 수가 "0" 일 경우
        return "0";
    return answer;
}

" 문제를 보고 !!정렬의 기준!! 을 어떻게 설정할지 고민하라. "

---

• [ CheckPoint ]

1.  to.string( 정수 ) 를 기억하자.
   = 정수를 문자열로 반환해주는 함수 ( #include <string> 필요 )
2. C++반복문은 ( 일반적 반복문, iterator이용, auto방식 3가지 정도는 기억 )
3. 나는 정렬의 기준을 깔끔하게 잡지 못하고, 숫자벡터의 요소들의 최고자리수를 먼저 구해서 정렬시키고, 최고자리수가 같은 경우 원래 숫자벡터끼리 모든 자리수를 구한 값이 같으면 그대로 두는 식....( 내가 설명하고도 뭔소린지 이해 못한다..) (생략)
4.  결론적으로, 숫자벡터를->문자열벡터로 변환한 벡터가지고서 각 원소들끼리 반복하면서 앞뒤 숫자끼리만 바꿔보면서 더 큰 숫자가 만들어지면 Swap하는 식으로 정렬한 다음, 정답 벡터에 넣어주면 끝나는 문제였다.

[ 참고자료 ]