[프로그래머스 C++] 가장 큰 수

 

[프로그래머스 C++] 가장 큰 수

 

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

프로그래머스

---

 

 

해결방안

 

문자열 정렬

string 정렬

 

---

 

처음 시도한 코드 - 시간초과. DFS

 

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

vector<string> newNum;
int ch[1001];
int maxNum;

void DFS(vector<int>& v, int x, string s)
{
    if(x == v.size()){
        newNum.push_back(s);
        maxNum = max(maxNum, stoi(s));
        return;
    }

    for(int i=0; i<v.size(); i++)
    {
        if(ch[i] == 0)
        {
            ch[i] = 1;
            DFS(v, x + 1, s + to_string(v[i]));
            ch[i] = 0;
        }	    
    }
}

string solution(vector<int> numbers) {

    DFS(numbers, 0, "");

    return to_string(maxNum);
}

 

 

---

 

두번째 시도한 코드 - 시간초과. DFS + 앞자리가 가장 큰 숫자부터 시작

 

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

vector<string> newNum;
int ch[1001];
int maxNum;

void DFS(vector<int>& v, int x, string s)
{
    if(x == v.size()){
        newNum.push_back(s);
        maxNum = max(maxNum, stoi(s));
        return;
    }

    for(int i=0; i<v.size(); i++)
    {
        if(ch[i] == 0)
        {
            ch[i] = 1;
            DFS(v, x + 1, s + to_string(v[i]));
            ch[i] = 0;
        }	    
    }
}

string solution(vector<int> numbers) {

    int start = 0;
    int firstNum=0;
    for(int i=0; i<numbers.size(); i++)
    {
        string temp = to_string(numbers[i]);

        if(firstNum < temp[0] - '0'){
            firstNum = temp[0] - '0';
            start = i;
        }
    }

    ch[start] = 1;
    DFS(numbers, 1, to_string(numbers[start]));
    
    return to_string(maxNum);
}

 

 

---

 

 

정답 코드

 

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

vector<string> strNums; // 숫자들을 문자열로 변환하여 저장

// 문자열 비교 함수. a와 b를 이어붙인 결과가 b와 a를 이어붙인 결과보다 크면 true 반환
bool Compare(string& a, string& b){
    return a + b > b + a;
}

string solution(vector<int> numbers) {

    for (int i = 0; i < numbers.size(); i++)
    {
        strNums.emplace_back(to_string(numbers[i])); // 모든 원소를 문자열로 변환하여 strNums에 저장
    }
    sort(strNums.begin(), strNums.end(), Compare); // Compare 함수를 기준으로 strNums 벡터를 내림차순 정렬

    string answer;
    for(int i=0; i<strNums.size(); i++) // strNums의 모든 원소를 answer에 이어 붙임
    {
        answer += strNums[i];
    }
    
    return answer[0] == '0' ? "0" : answer; // 만약 answer의 첫 글자가 '0'이라면 "0"을 반환, 그렇지 않으면 answer 반환
}

int main()
{
    vector<int> testcase1 = { 6, 10, 2 };
    vector<int> testcase2 = { 3, 30, 34, 5, 9 };
    vector<int> testcase3 = { 123, 1232 }; //1232123
    vector<int> testcase4 = { 0, 0 }; // 0
    
    cout << solution(testcase1);

	return 0;
}