프로그래머스 - 가장 큰 수

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

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

 

처음에 next_permutation 으로 브루트포스 방식으로 전체를 돌려서 할려 했으나

시간 초과가 나서 통과가 불가능했다.

c++ 에서 제공하는 string 은 비교 연산자를 자체적으로 가지고 있는데,

"123" 과 "1234" 를 비교하면, "1234" 가 더 큰 값으로 처리된다.

또한 이 문제에서 요구하는 것은 두 수를 합쳤을때, 더 큰 값이 나오게 만들기를 원한다.

"1" 과 "23" 이 있을때, "1" + "23" ("123") 보다는 "23" + "1" ("231") 이 더 크게 나와야 하는것.

그래서 정렬을 위한 별도의 함수 bool comp(string& a, string& b) 를 생성해주고

이것을 통해서 sort() 함수를 돌려주면 답이 나온다.

 

- c++

 

#include <bits/stdc++.h>
 
using namespace std;
 
bool comp(string& a, string& b) {
   return a + b > b + a;
}
 
string solution(vector<int> numbers) {
    string answer = "";
    
    vector<string> vec;
    for (int i = 0; i < numbers.size(); ++i) {
        string tmp = to_string(numbers[i]);
        vec.push_back(tmp);
    }
    
    sort(vec.begin(), vec.end(), comp);
    
    for (int i = 0; i < vec.size(); ++i) answer += vec[i];
    
    bool flag = true;
    for (int i = 0; i < answer.length(); ++i) {
        if (answer[i] != '0') {
            flag = false;
            break;
        }
    }
    
    if (flag) answer = "0";
    
    return answer;
}

 

 

 

 

 

 

 

 

- 테스트 케이스 참조

programmers.co.kr/questions/13432

프로그래머스