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

문제 링크

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

코딩테스트 연습 - 가장 큰 수

주어진 정수를 이어붙여서 만들 수 있는 가장 큰 수를 리턴하는 문제.

 

풀이

• 첫번째 아이디어

next_permutation을 이용해서 만들 수 있는 모든 정수 조합을 만든 뒤에 정렬을 이용해서 가장 큰 정수를 리턴한다.

물론 이 아이디어가 틀린 아이디어는 아니지만, 정수는 최대 100,000개가 주어진다. 그렇다면 우리가 할 수 있는 모든 조합의 경우의 수는 100000 팩토리얼 개의 경우가 있다. 가능한 경우의 수가 너무 많기때문에 시간초과 오류가 발생한다.

• 두번째 아이디어

먼저 주어진 정수를 문자열로 바꾼 후에, 정렬해준다.

문자열을 정렬하게 되면 사전순으로 정렬되기 때문에

"5" 와 "31"이 있다면 숫자상으로는 5 < 31 이지만 사전순으로는 "5" > "31" 이기 때문에 5가 앞선다.

정렬한 문자열들을 순서대로 이어 붙인다.

이 경우에는 예외가 발생한다.

만약 "3" 과 "30" 이 있다고 한다면, "30" > "3" 이기 떄문에 정렬 후 이어붙이면 "303"이 된다.

"303"은 "330"보다 작기 때문에 이런 경우 예외가 발생한다.

 

이 두 가지 아이디어 외에 도저히 어떻게 해야할지 생각이 안나서 고민끝에 결국 구글에 찾아보게 되었다.

멍토님의 블로그가 제일 위에 있어서 멍토님의 아이디어를 참고했다.

 

참고 링크

https://mungto.tistory.com/22

가장 큰 수 C++ (정렬)[프로그래머스]

 

정렬할 때, 두 문자열을 비교해서 두 문자열을 이어붙였을 때 더 큰 수를 만들 수 있도록 하는 수가 앞에 오도록 한다.

이게 무슨 말이나면 정렬할 때 두 수를 비교해서 정렬하게 되는데,

문자열 A와 B가 있다고 하자. AB > BA 면 A를 더 앞서는 것으로 판단한다.

아까처럼 "3" 과 "30" 이 있을 떄, "3" + "30" 을 하는 것이 "30" + "3"을 하는 것보다 더 큰 수를 만들 수 있다.

그렇기 때문에 정렬했을 때 "3"이 "30"보다 앞에 오도록 한다.

 

코드 작성

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
 
bool cmp(const string& a, const string& b){
    return a + b > b + a;
}
 
string solution(vector<int> numbers) {
    string answer = "";
    vector<string> nums;
    for(auto num : numbers)
        nums.push_back(to_string(num));
    sort(nums.begin(), nums.end(), cmp);
    if(nums[0] == "0")
        return "0";
    for(auto str : nums)
        answer += str;
    return answer;
}

비교함수를 내 임의로 정의할 때 문자열끼리 비교도 재정의가 가능한지 처음알았다.

내림차순으로 정렬할 때 외에는 써본적이 없었는데 오늘 새로운 사실을 알게됐다.