백준과 프로그래머스 양쪽 모두 올라와있지만 같은 풀이법으로 해결 가능하다.
https://school.programmers.co.kr/learn/courses/30/lessons/42746
https://www.acmicpc.net/problem/16496
난이도측정이 백준에는 플래티넘5인데 반해 프로그래머스는 Lv2라서 괴리감이 있는데
아이디어 자체는 플래티넘이 맞는데 풀이법은 Lv2가 맞긴해서 애매하긴 하다.
아이디어
문자열 { 3, 30, 34, 5, 9 }이 있을때 정렬 순서를 어찌해야 하는가가 핵심인데
처음엔 첫자리수가 가장 커야하니 큰 수가 앞으로 가야한다고 생각했다.
근데 그러면 { 9, 5, 34, 30, 3 }으로 정렬되는데 9534303보다 { 9, 5, 34, 3, 30 }으로 정렬된 9534330이 더 크므로 문제가 생긴다.
두번째 생각은 위의 문제를 해결하기 위해 더러운 해결법이지만 끝자리 숫자를 계속 이어붙여서 자릿수를 맞추는 방식을 생각했다.
예를들어 9면 9999로만들고, 5는 5555로, 34는 3444로, 30은 3000으로, 3은 3333으로 만든다.
이러면 정렬 결과 { 9999, 5555, 3444, 3333, 3000 } 이 되므로 원본으로 되돌리면 {9, 5, 34, 3, 30}순으로 정렬되므로 제대로 정렬된다.
하지만 위의 방법도 자릿수 제한이 분명 1000까지라 문제될건 없어보였는데 이상하게 특정 케이스들에서 계속 실패하기도 했고 풀이가 해결된다고 해도 좋은 알고리즘이 아니니 문제였다.
결국 해결 핵심 아이디어는 문자열x, 문자열y가 있을때 x + y와 y + x중 더 큰것을 선택하면 되는데
이걸 전체가 아니라 2개씩만 부분적으로 비교해서 정렬해도 전체로 봤을때 문제가 없다는 것이다.
예를들어 9와 5를 비교하면 95와 59중 95가 더 크니 9가 앞으로 간다.
9와 34를 비교할때 934와 349중 934가 더 크니 9가 앞으로 간다.
3과 30을 비교할때 330과 303중 330이 더 크니 3이 앞으로 간다.
이런식으로 전체 정렬을 하고나서 문자열에 시작부터 끝까지 넣어주면 부분들을 조건에 맞게 정렬했을 뿐인데 전체로도 제대로 정렬된다.
그러니 결국 compare 조건이 복잡하게 자릿수 늘리고, 첫자리 같은지 다른지 비교하고, 다음자릿수 같은지 다른지 더 큰지 작은지 비교할 필요도 없이 return x + y > y + x;로 한줄만 써도 끝이라는 것...
1) 백준 풀이
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false); cin.tie(NULL);
int N;
cin >> N;
vector<string> v(N);
for (int i = 0; i < N; i++) { cin >> v[i]; }
sort(v.begin(), v.end(), [](const string& a, const string& b) { return a + b > b + a; });
string answer = accumulate(v.begin(), v.end(), string{});
cout << (answer[0] != '0' ? answer : "0");
return 0;
}
2) 프로그래머스 풀이
#include <bits/stdc++.h>
using namespace std;
string solution(vector<int> numbers) {
vector<string> v(numbers.size());
transform(numbers.begin(), numbers.end(), v.begin(), [](int n) { return to_string(n); });
sort(v.begin(), v.end(), [](const string& a, const string& b) { return a + b > b + a; });
string answer = accumulate(v.begin(), v.end(), string{});
return answer[0] != '0' ? answer : "0";
}