백준 1422번 문제는 숫자의 신이라는 문제로, 주어진 숫자 카드를 조합하여 만들 수 있는 가장 큰 수를 구하는 문제입니다. 이 문제를 해결하기 위해선, 주어진 숫자들을 적절히 배열하여 가장 큰 수를 만들어야 합니다. 문제의 핵심은 숫자를 문자열로 취급하여 비교하는 것입니다. 문자열 비교를 통해 두 숫자를 이어 붙였을 때 더 큰 숫자를 만들 수 있는 순서를 찾아야 합니다.
접근 방법
문자열 비교를 위한 정렬: 주어진 숫자들을 문자열로 변환한 뒤, 문자열 비교를 통해 정렬합니다. 이때, 두 문자열 A, B를 비교할 때, AB와 BA를 비교하여 AB가 더 크면 A가 더 앞에 오도록 정렬합니다. 이렇게 하면 숫자를 이어 붙였을 때 가장 큰 숫자를 만들 수 있는 순서대로 정렬할 수 있습니다.
최대 숫자 채우기: 주어진 숫자 중 가장 큰 숫자를 찾아, K번 입력된 숫자 중 하나라면, 그 숫자를 필요한 만큼 추가로 채워 넣습니다. 이는 문제에서 요구하는 "입력받은 수 중 하나는 K번 반드시 사용해야 한다"는 조건을 만족시키기 위함입니다.
해결 방법
주어진 숫자를 모두 문자열로 변환합니다.
문자열로 변환된 숫자들을 위의 비교 방법으로 정렬합니다.
정렬된 숫자들을 이어 붙여 최종 결과를 만듭니다.
최대 숫자를 추가로 채워 넣는 과정을 수행합니다.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int N, K;
char ans[1000][11]; // 최대 K+N-1개의 문자열을 저장할 수 있어야 합니다.
char str[11];
// 비교 함수
int cmp(const void *a, const void *b) {
char first[22], second[22]; // 두 문자열을 연결할 임시 문자열
strcpy(first, *(const char**)a);
strcat(first, *(const char**)b);
strcpy(second, *(const char**)b);
strcat(second, *(const char**)a);
return strcmp(first, second) > 0 ? -1 : 1;
}
int main() {
scanf("%d %d", &K, &N);
str[0] = '\0'; // str을 빈 문자열로 초기화
for (int i = 0; i < K; i++) {
scanf("%s", ans[i]);
if (strlen(str) < strlen(ans[i]) || (strlen(str) == strlen(ans[i]) && strcmp(str, ans[i]) < 0)) {
strcpy(str, ans[i]); // str에 가장 큰 문자열 저장
}
}
for (int i = K; i < N; i++) {
strcpy(ans[i], str); // 가장 큰 문자열로 나머지를 채움
}
// ans 포인터 배열 생성
char* pointers[1000];
for (int i = 0; i < N; i++) {
pointers[i] = ans[i];
}
// 정렬
qsort(pointers, N, sizeof(char*), cmp);
// 출력
for (int i = 0; i < N; i++) {
printf("%s", pointers[i]);
}
return 0;
}