nums라는 숫자 목록이 주어질 때, 요소들의 순서를 재배열하여 만들 수 있는 가장 큰 수를 찾고, 그 결과를 문자열 형태로 반환해야 합니다.
예를 들어, 입력이 nums = [20, 8, 85, 316]이라면, 순서를 적절히 조합했을 때 가장 큰 수는 "88531620"이므로 출력 역시 "88531620"이 됩니다.
문제 접근 방법
이 문제는 다음과 같은 단계를 거쳐 해결할 수 있습니다.
- 임시 배열 temp를 하나 정의합니다.
- nums의 각 요소 i에 대해 다음을 수행합니다.
- i를 문자열로 변환한 뒤 temp에 삽입합니다.
- temp를 커스텀 비교 기준으로 정렬합니다. 두 문자열 a와 b를 비교할 때, 'a에 b를 이어 붙인 값(a+b)'이 'b에 a를 이어 붙인 값(b+a)'보다 크거나 같은지를 판단하여 정렬 순서를 결정합니다.
- 정렬된 temp의 각 문자열 s에 대해 다음을 수행합니다.
- 결과 문자열 res에 s를 차례대로 이어 붙입니다.
- 최종적으로 res를 반환합니다.
여기서 핵심은 단순 사전식(lexicographic) 정렬만으로는 최적의 답을 얻을 수 없다는 점입니다. 예를 들어 "3"과 "30"을 비교하면, 사전식으로는 "30"이 앞서지만 실제로 더 큰 수를 만들려면 "330"처럼 "3"이 먼저 와야 하기 때문입니다. 따라서 두 문자열을 서로 교차해서 붙여본 결과를 직접 비교하는 방식이 필요합니다.
아래 구현 예시를 통해 더 자세히 이해해 보겠습니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
static bool cmp(string a, string b) {
return (a + b) >= (b + a);
}
string solve(vector<int>& nums) {
vector<string> temp;
for (int i : nums) {
temp.push_back(to_string(i));
}
sort(temp.begin(), temp.end(), cmp);
string res;
for (string s : temp) {
res += s;
}
return res;
}
int main(){
vector<int> v = {20, 8, 85, 316};
cout << solve(v);
}
입력
{20, 8, 85, 316}
출력
88531620