가장 큰 수

문제 링크 => 코딩테스트 연습 - 가장 큰 수 | 프로그래머스 (programmers.co.kr)

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

---

조건에 맞게 정렬을 하는 문제이다.

 

예를 들어서 53, 535 가 주어졌다고 가정하자.

 

두 수를 붙여서 만들 수 있는 가장 큰 수를 확인하는 과정에서 다음과 같은 작업을 할 수 있다.

 

(1) 첫번째를 53, 두번째를 535 => 53535

(2) 첫번째를 535, 두번째를 53 => 53553

 

두 과정을 통해서 최대가 나오는 값은 53553 이므로 첫번째가 535, 두번째가 53 인 경우이다.

 

그러면 두 문자열을 붙여서 정수로 표현할 때, 더 커지도록 정렬을 하면 된다.

 

이러한 정렬을 하도록 compare 함수를 작성한다면 다음과 같다.

 

bool compare(string x, string y) {
	string tmp1 = x + y;
	string tmp2 = y + x;
	return stoi(&tmp1[0]) > stoi(&tmp2[0]);
}

 

그리고 정렬한 모든 값들을 이어주고 반환하면 된다.

 

그러나 [0, 0, 0, 0, 0] 이 들어온 경우? => 00000 이 된다.

 

모두 0인 경우가 반례인데 이러한 경우는 0만 반환하도록 따로 구현을 해줘야 한다. 

 

풀이 code

 

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

using namespace std;

bool compare(string x, string y) {
	string tmp1 = x + y;
    string tmp2 = y + x;
    return stoi(&tmp1[0]) > stoi(&tmp2[0]); 
}

string solution(vector<int> numbers) {
	string answer = "";

	vector<string> v;
	for (int i = 0; i < numbers.size(); i++) {
		v.push_back(to_string(numbers[i]));
	}
	sort(v.begin(), v.end(), compare);

    int op=0;
	for (int i = 0; i < v.size(); i++) {
		answer += v[i];
	    if(v[i] == "0") op++;
    }

    if(op == v.size()) return "0";
	return answer;
}