프로그래머스[Lv.2] - 가장 큰 수

문제 설명

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

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

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

프로그래머스

---

 

 

 

 

 

 

제한 사항

• numbers의 길이는 1 이상 100,000 이하입니다.
• numbers의 원소는 0 이상 1,000 이하입니다.
• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

---

 

 

 

 

 

 

풀이

정렬기준을 세워 정렬을 한 뒤 수를 이어붙이면 되는 문제이다.

즉, 정렬기준을 세우는 것이 핵심이다.

 

처음 문제를 풀 때는 비교할 숫자들을 한 자리씩 뜯어 비교하면 된다고 생각했다.

이때, 길이가 맞지 않으면 서큘러버퍼처럼 앞으로 돌아가 비교하면 된다고 생각했다.

만약 2234, 22가 있다면 만들 수 있는 수는 [223422, 222234]이다.

따라서, 돌아가서 비교하면 답을 구할 수 있다고 생각했다.

하지만 여기에는 반례가 존재했다. 

565, 56 이 있다면 내가 세운 기준으로 비교했을 때, 둘이 같은 순위를 갖는다.

하지만 결과는 명확히 다르다.

[56556, 56565] 가 만들어지니 확실히 큰 수를 만드는 방법이 존재한다.

 

따라서, 다른 접근법을 찾아야 했다.

문제의 목적은 큰 수를 만드는 것이다.

따라서 두 수를 이어 붙였을 때, 큰 수가 되는 순으로 정렬하면 되는 것이다.

위의 예제를 보면 56565가 56556보다 크다.

따라서 56이 앞에 있을 때 큰 수를 만들 수 있는 것이기 때문에 56이 565보다 앞에 존재하게 정렬을 진행한다.

이러한 논리대로 정렬을 진행한 뒤 수를 이어 붙이면 된다.

 

하지만, 여기서 주의할 점이 있다.

정답은 문자열로 return 하지만 근본적으로는 숫자이다.

따라서 모든 수를 이어 붙였을 때, 0이 되는 경우를 고려해야 한다.

숫자를 문자열로 바꾸어 이어 붙이면 "000"과 같은 경우가 생기기 때문에 정답 문자열이 모두 0이라면 "0"을 return 해야 한다.

---

 

 

 

 

 

전체 코드

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

using namespace std;

bool cmp(int a, int b)
{
    vector<int> aNum;
    vector<int> bNum;
    
    int originA = a;
    int originB = b;
    while(a >= 10)
    {
        aNum.push_back(a%10);
        a /= 10;
    }
    aNum.push_back(a);
    
    while(b >= 10)
    {
        bNum.push_back(b%10);
        b /= 10;
    }
    bNum.push_back(b);
    
    reverse(aNum.begin(), aNum.end());
    reverse(bNum.begin(), bNum.end());

    int tempA = originA;
    for(int i = 0; i < bNum.size(); i++)
    {
        tempA *= 10;
        tempA += bNum[i];
    }
    
    int tempB = originB;
    for(int i = 0; i < aNum.size(); i++)
    {
        tempB *= 10;
        tempB += aNum[i];
    }

    return tempA > tempB ? true : false;
}

string solution(vector<int> numbers) {
    string answer = "";
    
    sort(numbers.begin(), numbers.end(), cmp);
    
    for(auto num : numbers)
    {
        answer += to_string(num);
    }
    
    bool flag = true;
    for(auto a : answer)
    {
        if(a-'0' != 0)
        {
            flag = false;
            break;
        }
    }
    
    if(flag) answer = "0";
    
    return answer;
}

---