[프로그래머스 고득점kit] 정렬_가장 큰 수(c++)

https://school.programmers.co.kr/learn/courses/30/lessons/42746?language=cpp 

프로그래머스

보자마자 제일 앞 자릿수만 비교하면 되겠다 싶어 vector<pair<first_digit, idx> > 선언하고 정렬했는데 다음 자릿수를 걸러주지 못했다.

ex) 303, 340

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

using namespace std;

int get_first_digit(int n)
{
    int digit = -1, tmp = n;
    
    while (tmp > 0)
    {
        tmp /= 10;
        digit++;
    }
    return (n / pow(10, digit)); // 제일 앞자리수 리턴
}

bool    cmp(pair<int, int> a, pair<int, int> b)
{
    return (a.first > b.first);
}

string solution(vector<int> numbers) 
{
    string answer = "";
    vector<pair<int, int> > v(numbers.size()); // 앞자리수, idx
    
    for (int i = 0; i < numbers.size(); i++)
        v[i] = make_pair(get_first_digit(numbers[i]), i);
    sort(v.begin(), v.end(), cmp);
    for (int i = 0; i < numbers.size(); i++)
        answer += to_string(numbers[v[i].second]);
    return answer;
}

그래서 다음 자릿수도 비교하게 해줬는데  시간초과가 났다. 다른 방법을 찾아서...

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

using namespace std;

int get_first_digit(int n, int depth)
{
    int digit = -1, tmp = n;
    
    while (tmp > 0)
    {
        tmp /= 10;
        digit++;
    }
    if (digit - depth < 0) // 자릿수보다 큰 digit으로 나눠야 할때
        return (1);
    return (n / pow(10, digit - depth)); // 제일 앞자리수 리턴
}

bool    cmp(pair<int, int> a, pair<int, int> b)
{
    int i = 0;
    int first_a, first_b;
    if (a.first == b.first)
        return (true);
    while (i < 3)
    {
        first_a = get_first_digit(a.first, i);
        first_b = get_first_digit(b.first, i);
        if (first_a != first_b)
            return (first_a > first_b);
        i++;
    }
    return (first_a > first_b);
}

string solution(vector<int> numbers) 
{
    string answer = "";
    vector<pair<int, int> > v(numbers.size()); // 앞자리수, idx
    
    for (int i = 0; i < numbers.size(); i++)
        v[i] = make_pair(numbers[i], i);
    
    sort(v.begin(), v.end(), cmp);
    for (int i = 0; i < numbers.size(); i++)
        answer += to_string(numbers[v[i].second]);
    return answer;
}

그래서 그냥 자릿수를 먼저 구해주고 비교해주는 식으로 했다. 이러니까 34, 3을 구분 못해준다 환장하겠네 진짜

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

using namespace std;

int get_digit(int n)
{
    int digit = -1;
    while (n > 0)
    {
        n /= 10;
        digit++;
    }
    return (digit);
}

int get_n_devided_by_digit(int n, int digit)
{   
    return (n / pow(10, digit)); // 제일 앞자리수 리턴
}

bool    cmp(pair<int, int> a, pair<int, int> b)
{
    int i = 0;
    int diff_digit_ab = get_digit(a.first) - get_digit(b.first);
    
    if (diff_digit_ab == 0)
        return (a.first > b.first);
    else if (diff_digit_ab < 0)
        return (a.first > get_n_devided_by_digit(b.first, diff_digit_ab * (-1)));
    else
        return (get_n_devided_by_digit(a.first, diff_digit_ab) > b.first);
}

string solution(vector<int> numbers) 
{
    string answer = "";
    vector<pair<int, int> > v(numbers.size()); // 앞자리수, idx
    
    for (int i = 0; i < numbers.size(); i++)
        v[i] = make_pair(numbers[i], i);
    
    sort(v.begin(), v.end(), cmp);
    for (int i = 0; i < numbers.size(); i++)
        answer += to_string(numbers[v[i].second]);
    return answer;
}

나눠주니까 마지막 자릿수가 버려져서 곱하기로 바꿔줬다. 근데 또 실패...

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

using namespace std;

int get_digit(int n)
{
    int digit = -1;
    while (n > 0)
    {
        n /= 10;
        digit++;
    }
    return (digit);
}

// int get_n_devided_by_digit(int n, int digit)
// {   
//     return (n / pow(10, digit)); // 제일 앞자리수 리턴
// }

bool    cmp(pair<int, int> a, pair<int, int> b)
{
    int i = 0;
    int diff_digit_ab = get_digit(a.first) - get_digit(b.first);
    
    if (diff_digit_ab == 0)
        return (a.first > b.first);
    else if (diff_digit_ab < 0)
        return (a.first * pow(10, diff_digit_ab * -1) > b.first);
    else
        return (a.first > b.first * pow(10, diff_digit_ab));
}

string solution(vector<int> numbers) 
{
    string answer = "";
    vector<pair<int, int> > v(numbers.size()); // 앞자리수, idx
    
    for (int i = 0; i < numbers.size(); i++)
        v[i] = make_pair(numbers[i], i);
    
    sort(v.begin(), v.end(), cmp);
    for (int i = 0; i < numbers.size(); i++)
        answer += to_string(numbers[v[i].second]);
    return answer;
}

[979, 97, 978, 81, 818, 817]
답 9799797881881817

이걸 못 걸러준다... 970 보다 978이 더 크니 내 풀이대로는 978이 먼저 오게 된다.

너무 오래 잡혀있어서 구글링을 해 보니 기가 막힌 방법이 있었다.

애초에 string으로 받아서 a+b, b+a를 비교하는 방법이었다.... 보고 소름이 쫙 돋아버렸다. 더 열심히 풀어서 실력을 길러보자 파이팅~

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

using namespace std;

bool    cmp(string a, string b)
{
    return (a + b > b + a); //어의가없네
}

int zero_vector(vector<int> numbers)
{
    for (int i = 0; i < numbers.size(); i++)
        if (numbers[i])
            return (0);
    return (1);
}

string solution(vector<int> numbers)
{
    string answer = "";
    vector<string> v(numbers.size());
    if (zero_vector(numbers))
        return (answer + "0");
    
    for (int i = 0; i < numbers.size(); i++)
        v[i] = to_string(numbers[i]);
    
    sort(v.begin(), v.end(), cmp);
    for (int i = 0; i < numbers.size(); i++)
        answer += v[i];
    return answer;
}