[Programmers] Lv2. 가장 큰 수 | C++

🔗문제 보러가기

프로그래머스

 

👨‍💻풀이 과정

 

별 거 아닌 문제라고 생각했는데, 생각보다 오래 걸려 버렸네요... 주어진 숫자를 문자열에 담아, 3배만큼 키운 후 비교해주었습니다. 예를 들어,

// 한 자리 숫자일 경우
"5" -> "555"

// 두 자리 숫자일 경우
"45" -> "454545"

// ...

 

3배로 해주는 이유는 최소 자릿수가 한 자리이기 때문이죠. 4배를 해주게 되면, 입력 데이터 범위 최댓값인 1000을 넘어가게 됩니다. 아무튼, 변환을 완료했으니, 다음 기준에 따라 정렬해주면 됩니다.

 

1. 맨 앞 자리부터 비교해가며, 큰 수가 앞으로 가도록 한다.
2. 큰 수가 없다면, 두 변환된 수의 길이를 확인한다. 두 길이가 같다면 똑같은 수이므로, false 리턴
3. 그게 아니라면, 길이가 작은 쪽이 앞으로 가도록 한다.
4. 합칠 문자열들이 모두 '0'으로만 이루어져 있다면, "0"을 리턴하는 예외 처리를 해줘야 한다.

 

✏️소스 코드 및 결과

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
const int MULTIPLY = 3;

class Data {
public:
    Data() { }
    Data(int num) {
        originNumber = to_string(num);
        for (int i = 0; i < MULTIPLY; i++)
            convertedNumber += originNumber;
    }

    bool operator<(const Data& other) {
        for (int i = 0; i < convertedNumber.length() and i < other.convertedNumber.length(); i++) {
            if (convertedNumber[i] == other.convertedNumber[i])
                continue;
            return convertedNumber[i] > other.convertedNumber[i];
        }

        if (convertedNumber.length() == other.convertedNumber.length())
            return false;
        return convertedNumber.length() < other.convertedNumber.length();
    }
    
public:
    string originNumber;
    string convertedNumber;
};

string solution(vector<int> numbers) {
    vector<Data> myData;
    bool isZero = true;

    for (const auto element : numbers) {
        if (element != 0 and isZero) {
            myData.emplace_back(Data(element));
            isZero = false;
            continue;
        }

        myData.emplace_back(Data(element));
    }

    if (isZero)
        return "0";

    sort(myData.begin(), myData.end());
    string answer = "";

    for (const auto element : myData)
        answer += element.originNumber;
    return answer;
}