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

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

프로그래머스 가장 큰 수 문제입니다.

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

문제

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 구합니다.

주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이 중 가장 큰 수는 6210입니다.

• 제한 사항
  • 0 또는 양의 정수가 담긴 배열 numbers의 길이는 1 이상 100,000 이하입니다.
  • numbers의 원소는 0 이상 1,000 이하입니다.
  • 정답이 클 수 있으므로 문자열로 바꾸어 return 합니다.

생각한 아이디어

• [6, 10, 2] 에서 문자들을 서로 결합해 봅니다.

즉, numbers에 담긴 원소들을 특정한 기준에 의해 정렬하면 됩니다.

• 이 특정한 기준은, 두 원소들 간에 서로 결합해 보고 사전 순서상 더 뒤에 오게 되는 숫자가 앞으로 가도록 정렬하는 것입니다.
• 두 원소간 결합을 하면 나오는 경우의 수 2가지의 자릿수는 동일할 것이므로, 사실상 사전 순서상 뒤에 오는 것이 숫자로 볼 때 더 큰 숫자를 의미하게 됩니다. (예 : 10과 2는 ‘102’와 ‘210’을 만들 수 있음)
• 최종적으로 결합할 때 앞에서부터 더해주기만 하면 되도록 하기 위해 위와 같은 정렬과정을 거칩니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

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

using namespace std;

bool cmp(const string &a, const string &b) {
    if (a + b > b + a)
        return true;
    else
        return false;
}

string solution(vector<int> numbers) {
	string answer = "";
	vector<string> strArr;
	for (int i = 0; i < numbers.size(); i++) {
		strArr.push_back(to_string(numbers.at(i)));
	}
	sort(strArr.begin(),strArr.end(),cmp);
	for (string str : strArr) {
		answer += str;
	}
	if (answer[0] == '0')
		return "0";
	return answer;
}

• 정렬 함수를 작성하는 것이 관건입니다.
• 앞서 말했듯 두 문자를 결합해 보고 사전순서가 더 뒤인 것 (즉, 문자열 에서는 부등호 비교할 때 더 큰 쪽이 사전 순서가 더 뒤임을 말합니다) 을 앞에 있게끔 합니다.
• bool type의 compare 함수에서, return true를 반환하는 것은 그 순서를 그대로 유지 한다는 것입니다.
  • 즉, if문 조건에 의해 문자를 결합해 보았을 때 더 컸다면 그 순서를 그대로 둡니다.
  • 만일, 그렇지 않았다면 순서를 뒤바꿔야 합니다.

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges