안녕하세요,
재재입니다.
boj 16496 큰 수 만들기 문제에 대한 솔루션입니다.
(1) 문제 설명
분류: greedy
출처: https://www.acmicpc.net/problem/16496
(1000이하) N개의 수가 주어진다.
주어진 수를 나열해서 최대의 숫자를 만들어주면 된다.
(단, leading zeroes 를 지울 것)
(2) Wrong Answer 코드
단순히 생각해보면, 숫자를 각 자리수를 기준으로 역순으로 정렬해서 큰 숫자부터 작은 숫자를 써주면된다.
9, 53, 35, 3, 32, 1000
3 보다는 35가 앞에 오는게 이득이고,
32보다는 3이 앞에 오는게 이득입니다.
여기까지만 생각해서 구현해보면 아래와 같습니다.
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int cnts[10];
char str[12];
int main() {
int n;
scanf("%d", &n);
vector <string> streams;
string ans = "";
for (int i = 0; i < n; i++) {
scanf("%s", str);
if (strlen(str) == 1) {
cnts[str[0] - '0']++;
}
else {
streams.emplace_back(string(str));
}
}
sort(streams.begin(), streams.end());
for (int i = streams.size() - 1; i >= 0; i--) {
int digit = streams[i][0] - '0';
for (int j = 9; j > digit; j--) {
while (cnts[j] > 0) {
cnts[j]--;
ans += to_string(j);
}
}
if (cnts[digit] > 0) {
if (streams[i][0] > streams[i][1]) {
while (cnts[digit] > 0) {
cnts[digit]--;
ans += to_string(digit);
}
ans += streams[i];
}
else {
if (i == 0 || streams[i - 1][0] != streams[i][0]) {
ans += streams[i];
while (cnts[digit] > 0) {
cnts[digit]--;
ans += to_string(digit);
}
}
else {
ans += streams[i];
}
}
}
else {
ans += streams[i];
}
}
for (int j = 9; j >= 0; j--) {
while (cnts[j] > 0) {
cnts[j]--;
ans += to_string(j);
}
}
if (ans[0] == '0')printf("0\n");
else {
printf("%s\n", ans.c_str());
}
}
그런데 이제 아래와 같은 숫자가 추가되면 골치가 아파집니다.
9, 53, 35, 3, 30, 101, 10, 1000
(3) BOJ 16496 풀이 도출
위의 WA 코드를 좀 더 개선해보겠습니다.
위에서 틀렸던 부분을 조금 더 발전시킨 아이디어는 다음과 같습니다.
“임의의 두 숫자를 a, b를 나열해서 높은 경우” 를 한번 생각해본다면,
이 문제의 풀이에 좀 더 가까워 질 수 있습니다.
ab 와 ba 중 더 큰 숫자는?
임의의 두 문자열을 붙여서 비교 할 수 있다면,
이 문제를 쉽게 해결 할 수 있습니다.
N 은 1000이기 때문에 가장 쉬운 정렬로
$$ O(N^2) $$
조금 더 빠른 정렬로는
$$ O(Nlog(N)) $$
이 가능합니다.
(4) 정답 코드
BOJ 16496 큰 수 만들기