[프로그래머스/Lv2] - 가장 큰 수

 

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

코딩테스트 연습 - 가장 큰 수

• 입력을 조합하여 만들 수 있는 가장 큰 수를 찾는 문제이다.
• 처음에 1, 10 등이 들어와도 4자리로 맞춰서 문제를 해결할려고 했으나 1~6 테스트 케이스에서 계속 실패가 발생하였다.
• 오히려 sort()를 사용할 때 2개의 숫자로 조합할 수 있는 수를 비교하는 것이 정답이었다.

---

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

using namespace std;

// global
struct DATA {
    int number;
    string str;
};

bool sorting(DATA lhs, DATA rhs)
{
    int num1 = atoi(string((lhs.str) + (rhs.str)).c_str());
    int num2 = atoi(string((rhs.str) + (lhs.str)).c_str());

    if (num1 <= num2)
        return false;

    return true;
}

string solution(vector<int> numbers) {
    string answer = "";

    // set data
    vector<DATA> calcSrc;
    for (int number : numbers)
    {
        DATA data;
        char buff[5] = { 0, };
        sprintf(buff, "%d", number);

        data.number = number;
        data.str = buff;

        calcSrc.push_back(data);
    }

    // sort
    sort(calcSrc.begin(), calcSrc.end(), sorting);

    // answer
    for (auto item : calcSrc)
    {
        answer += item.str;
    }

    auto ansIter = answer.begin();
    while (ansIter != answer.end())
    {
        int pos = ansIter - answer.begin();
        if (0 == pos && 1 != answer.size() && '0' == (*ansIter))
        {
            ansIter = answer.erase(ansIter);
            continue;
        }
        ++ansIter;
    }

    return answer;
}

int main()
{
    //vector<int> numbers = { 12, 1213, 333 ,33, 31 , 323, 34 };
    //vector<int> numbers = { 0, 0, 0 };
    //vector<int> numbers = { 11, 112, 9 };

    /*
    * 1/101/x10
    * 1/10/101
    */
    //vector<int> numbers = { 1, 101, 10, 1000 };

    vector<int> numbers = { 12,121 }; // 12121
    vector<int> numbers2 = { 10, 101 }; // 10110
    vector<int> numbers3 = { 3, 30 }; // 220200

    string ans = solution(numbers);
    printf("ans : %s\n", ans.c_str());

    ans = solution(numbers2);
    printf("ans : %s\n", ans.c_str());

    ans = solution(numbers3);
    printf("ans : %s\n", ans.c_str());

    return 0;
}