<백준 알고리즘> 16496번: 큰 수 만들기

문제

음이 아닌 정수가 N개 들어있는 리스트가 주어졌을 때, 리스트에 포함된 수를 나열하여 만들 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 리스트에 포함된 수가 주어진다. 수는 공백으로 구분되어져 있고, 1,000,000,000보다 작거나 같은 음이 아닌 정수 이다. 0을 제외한 나머지 수는 0으로 시작하지 않으며, 0이 주어지는 경우 0 하나가 주어진다.

출력

리스트에 포함된 수를 나열하여 만들 수 있는 가장 큰 수를 출력한다. 수는 0으로 시작하면 안되며, 0이 정답인 경우 0 하나를 출력해야 한다.

예제 입력 1

5 3 30 34 5 9

예제 출력 1

9534330

예제 입력 2

5 0 0 0 0 1

예제 출력 2

10000

---

Solution

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int compare(char *a,char *b)
{
	int len_a=strlen(a), len_b=strlen(b);
	char *a_first=NULL, *b_first=NULL;

	if(len_a<len_b)
	{
		for(int i=0;i<len_b;i++)
			if(a[i%len_a]<b[i])
				return 1;
			else if(a[i%len_a]>b[i])
				return -1;
	}
	else
	{
		for(int i=0;i<len_a;i++)
			if(a[i]<b[i%len_b])
				return 1;
			else if(a[i]>b[i%len_b])
				return -1;
	}

	a_first=(char *)calloc(len_a+len_b,sizeof(char));
	strcpy(a_first,a);
	strcat(a_first,b);
	b_first=(char *)calloc(len_a+len_b,sizeof(char));
	strcpy(b_first,b);
	strcat(b_first,a);

	for(int i=0;i<len_a+len_b;i++)
		if(a_first[i]<b_first[i])
		{
			free(a_first);
			free(b_first);
			return 1;
		}
		else if(a_first[i]>b_first[i])
		{
			free(a_first);
			free(b_first);
			return -1;
		}

	free(a_first);
	free(b_first);
	return 1;
}

int main(void)
{
	int N;
	char **list=NULL;

	scanf("%d", &N);
	list=(char **)malloc(N*sizeof(char *));
	for(int n=0;n<N;n++)
	{
		list[n]=(char *)calloc(11,sizeof(char));
		scanf("%s", list[n]);
	}

	for(int i=0;i<N;i++)
		for(int j=i+1;j<N;j++)
			if(compare(list[i],list[j])>0)
			{
				char temp[11]={'\0', };
				strcpy(temp,list[i]);
				strcpy(list[i],list[j]);
				strcpy(list[j],temp);
			}

	if(list[0][0]=='0')
		printf("0\n");
	else
	{
		for(int n=0;n<N;n++)
			printf("%s", list[n]);
		printf("\n");
	}

	for(int n=0;n<N;n++)
		free(list[n]);
	free(list);
	return 0;
}