2025.3.26 알고리즘 코드카타

알고리즘 코드카타 - 103. 가장 큰 수

문제 링크

문제 설명

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 <vector>
#include <algorithm>

using namespace std;

bool compare(string a, string b)
{
    // 비교 문자열 길이가 같을 경우
    if(a.size() == b.size())
    {
        if(a.size() > 1 && a[0] == b[0]) 
        {
            if(a.size() > 2 && a[1] == b[1])
            {
                return a[2] > b[2];
            }
            return a[1] > b[1]; 
        }
        return a > b;
    }
    // 자리수가 다를 경우
    else if(a.size() != b.size())
    {
        int ab = stoi(a + b);
        int ba = stoi(b + a);
        if(ab > ba) return ab > ba;
        else if(ba > ab) return ab > ba;
    }
}
string solution(vector<int> numbers) {
    string answer = "";
    // 자리수 기준 정렬 같으면 두번째 자리, 세번째 자리
    vector<string> string_numbers;
    for(int num : numbers)
    {
        string_numbers.push_back(to_string(num));
    }
    
    sort(string_numbers.begin(), string_numbers.end(), compare);
    
    for(string num : string_numbers)
    {
        answer += num;
    }
    
    // numbers의 모든 원소가 0일 경우
    int countifzero = count(string_numbers.begin(), string_numbers.end(), "0");
    if(countifzero == string_numbers.size())
    {
        answer = "0";
    }
    
    return answer;
}

• 질문 수가 엄청나게 많아서 겁먹었는데, 이 문제는 커스텀 정렬함수를 원하는 대로 만들 수 있는가? 를 판단하는 문제였던 것 같다.

• 주어진 배열의 길이, 원소의 크기가 그렇게 크지 않아 시간복잡도의 압박이 덜하기 때문.

  • 배열의 최대 크기가 더 컸다면 정렬 알고리즘의 시간복잡도까지 신경써야 해서 더 까다로웠을 것이다.
  • 그런데 sort() 쓸 거면 O(N log N) 이라 어차피 상관이 없을듯

• 코드의 구조는 간단하다. 자리수 비교를 위해 주어진 정수 배열을 문자열 배열로 바꾸고, 정렬한 다음, 한 문자열에 이어 붙이면 된다.

• 정렬 함수의 구조는 다음과 같다.

  1. 왼쪽부터 첫 번째 문자를 서로 비교한다.
  2. 같으면 두 번째, 그것도 같으면 세 번째 문자를 비교한다.
     (정수 크기가 최대 1000이므로 세 번째 자리까지만 비교)
  3. 만약 두 문자열의 길이가 다르면 (예: 3과 30) 두 문자열을 순서를 바꿔 이어붙인 결과로 비교한다.

• 모든 원소가 0으로 구성된 정수 배열이 있을 수도 있으니 (이 부분에서 틀려서 질문방을 보고 알았다.) 해당 부분 예외 처리도 해준다.
  내림차순 정렬을 하니 첫 번째 원소가 0인지만 확인하면 되는데, 여기서는 멍청하게 배열 크기와 0의 개수를 비교했다.

• 그리고 다른 사람의 풀이를 보니 자리수가 다른 경우의 비교법만 사용해도 충분히 가능했다. 30과 34를 비교할 때 당연히 3034보단 3430이 더 크니까..