프로그래머스 2023.10.29 (2Lv 가장 큰 수)

프로그래머스

문제

---

문제 설명
0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.
예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.
0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

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

입출력 예

numbers	return
[6, 10, 2]	"6210"
[3, 30, 34, 5, 9]	"9534330"

코딩

---

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

using namespace std;

bool compare(int _num1, int _num2)
{
    string str_num1 = to_string(_num1);
    string str_num2 = to_string(_num2);

    int num1 = stoi(str_num1 + str_num2);
    int num2 = stoi(str_num2 + str_num1);

    return num1 > num2;
}

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

    sort(numbers.begin(), numbers.end(), &compare);
    
    bool bZero = true;

    for (size_t i = 0; i < numbers.size(); ++i)
    {
        if (numbers[i] != 0)
            bZero = false;

        answer += to_string(numbers[i]);
    }

    if (bZero)
        answer = "0";

    return answer;
}

오늘 풀었던 스킬 체크 두번 째 문제였다.

이번 문제는 이전 DP문제와 다르게 쉽게 풀 수 있었다.

 

문제를 보자마자 정렬을 이용하면, 쉽게 풀 수 있을 것 같다는 생각을 했다.

다만, 단순히 오름차순, 내림차순으로 정렬할게 아니라 주어진 두 수를 조합할 수 있는 2가지 경우중 가장 큰수가 나오는 경우대로 정렬해주면 된다.

 

생각보다 빠르게 풀어서 안심했지만, 생각지 못한 예외상황이 발생했다.

테스트 11번 만 실패가 떴는데 이유는 0, 0, 0, 0이 주어지면, answer의 결과가 "0000"이 나오기 때문이었다.

즉, 0일 때만 예외 처리를 해주면 됐는데, 가장 처음 생각한 방법이 완성된 수에 1을 곱해주는 것이었다.

 

하지만, 문제에서도 주어졌듯이 완성된 수가 매우 클 수 있기 때문에 int나 long long 자료형으로는 완성된 수를 표현할 수 없어 문제가 발생핬다.

 

때문에 정렬한 수를 문자열로 변환해 더해주는 과정에서 해당 수가 0인지 아닌지를 확인해, 만약 0이 아닌 수가 나온적이 없다면 "0"을 답으로 제출하도록 변경해주었다.

 

단순 정답을 문자열로만 제출하면 된다고 생각하고, 예외상황은 생각하지 않았기 때문에 문제가 됐던거 같다.

 

실행 결과

---