Algorithm

[Algorithm] 프로그래머스 C++ : 가장 큰 수

dokylee 2020. 8. 18. 18:36

 

 

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

 

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

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 ��

programmers.co.kr

원래는 next_permutation을 써서 전체 경우의 수에 대해 계산을 했는데

 

자꾸 실패가 떠서

 

사용자함수로 sort하는 방법을 알게 됐다

 

cmp함수를 만들어서 sort()에 넣어주면 된다

 

이 경우 두 숫자의 우위를 정하는 방법은 스트링두개를 합쳤을 때, 더 큰 수가 우위를 점하게 되는 것이므로

 

a+b>b+a를 리턴하도록 하고

 

나머지는 뭐 integer에서 string 변환하는 부분만 해주면 된다

 

 

** 놓칠 수 있는 부분

[0, 0]일 경우 "00"이 반환되는데

그게 안되도록 정렬후 배열의 맨 첫자리가 0일 시 뒷자리 모두 0일 것이므로 "0"을 반환하게 한다

 

 

 

 

Code

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

using namespace std;

bool cmp(string a, string b) {
    return a + b > b + a;
}

string solution(vector<int> numbers) {
    string answer = "";
    vector<string> numbers_str;
    
    // numbers 벡터를 스트링벡터로 바꾸기
    for(int i: numbers) numbers_str.push_back(to_string(i));
    
    // 사용자 함수 cmp로 정렬
    sort(numbers_str.begin(), numbers_str.end(), cmp);
    
    // numbers_str의 원소들을 다 합치기
    for(string str: numbers_str) answer+=str;
    
    // 처음 수가 0이면 뒤 수도 모두 0이므로 0반환
    if (answer[0] == '0') return "0";
    
    return answer;
}