[프로그래머스] 가장 큰 수

■ 문제 설명

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

 

 

▶ 내가 푼 코드

 

문제 풀 때 굉장히 애를 먹었던 문제이다.

기본 테스트 케이스는 쉽게 통과하지만 예외 처리 케이스를 생각해내기 굉장히 까다로운 문제이다.

 

우선 기본적인 아이디어는 다음과 같았다.

 

string으로 비교하기 위해 str vector에 삽입 후 sort로 정렬해준 뒤 출력하는 것이다.

 

만약 case 1) 과 같이 a[0]과 b[0]이 같은 경우 자기 자신을 그대로 복사하여 비교해준다.

 

예를들면 3과 34의 경우 "343"이 되어야한다.

첫번째가 같으므로 자기 자신인 3을 복사하여 비교하면 33 < 34가 크기 때문에 343을 출력 할 수 있다.

 

 

그렇지 않고 9와 3같이 다른 수는 바로 case 2)로 넘어가고 내림차순으로 정렬되어 출력할 수 있도록 코드를 짰다.

#include <string.h>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

bool cmp(string a, string b){
    
    for(int i=0;;i++){
        //exeption
        if(a == b) return a>b;
        
        //case 1) a[i] == b[i]
        if(a[i] == b[i]){
            //case 1.1) a.length() == b.length()
            if(a.length() == b.length())
                continue;
            //case 1.2) a.length() != b.length()
            if(a.length() < b.length()){
                a += a;
            }else{
                b += b;
            }
        //case 2) a[i] != b[i]
        }else
            return a[i] > b[i]; // 내림차순 정렬
    }
}

string solution(vector<int> numbers) {
    string answer = "";
    vector<string> str;
    
    //int to string
    for(int i=0;i<numbers.size();i++){
        str.push_back(to_string(numbers[i]));
    }
    
    //sorting
    sort(str.begin() , str.end(), cmp);
    
    //add answer
    for(int i=0;i<str.size();i++)
        answer += str[i];
    
    return answer;
}

하지만 여기서 내가 생각하지 못한 부분이 있었다.

 

① [0, 0, 0, 0] 일 경우 "0"을 return 해야한다.

/* 기존 코드 */
return answer;

/* 수정 코드 */
if(answer[0] == '0') return "0";
else return answer;

이 부분은 사람들이 올린 질문 글들을 보고 쉽게 찾아서 고칠 수 있었다.

 

② 시간 및 메모리 초과

 

예외 케이스를 처리하고 질문글에 있는 모든 테스트 케이스를 통과하였으나 시간과 메모리 초과가 떴다.

결론적으로는 이를 해결하지 못했다.

아무래도 수가 커질 경우 cmp함수 안에서 메모리를 많이 쓰는 것 같은데 해결 방법을 찾지 못했다.

 

 

다른 블로그를 보던 중 cmp함수를 아주 간단하게  풀 수 있었다. 

 

#include <algorithm>
#include <string>
#include <vector>
 
using namespace std;
 
bool comp(const string &a, const string &b)
{
    if (b + a < a + b)
        return true;
    return false;
}
 
string solution(vector<int> numbers) {
    string answer = "";
 
    vector<string> arr;
 
    for (int i=0; i<numbers.size(); i++) {
        arr.push_back(to_string(numbers[i]));
    }
 
    sort(arr.begin(), arr.end(), comp);
 
    for (auto iter = arr.begin(); iter < arr.end(); ++iter)
        answer += *iter;
 
    if (answer[0] == '0')
        answer = "0";
 
    return answer;
}

출처: https://bitwise.tistory.com/373 [Bitwise]

 

답을 알고나니 바보가 된 기분이였다.

 

그래도 이 문제 덕분에 sort함수의 사용자 정의 함수로 정렬하는 법을 알고

블로그에 정리도 할 수 있어서 나름 의미있는 문제였다.

 

 

※ 출처 : https://programmers.co.kr/learn/courses/30/lessons/42746?language=cpp#

코딩테스트 연습 - 가장 큰 수 | 프로그래머스