백준 1422 숫자의 신 C++

https://www.acmicpc.net/problem/1422

1422번: 숫자의 신

입력으로 주어진 수들로 만들 수 있는 최대 수를 구하는 문제입니다. 다만 입력으로 주어진 모든 수를 사용해야하며 중복으로 고를 수 있습니다.

 

k개의 수와 n개의 택을 할 때 어떻게든 가장 큰 수를 뽑기 위해서는 가장 큰 수를 최대한 많이 골라 이어 붙혀야 합니다.

ex. 1, 23, 456 / 5개 택 => 456 23 1 1 1 < 456 456 456 23 1 

 

또한 10 100 을 이어 붙혔을 때 10 100 > 100 10 인 경우도 있고,

25 256을 이어 붙혔을 때 25 256 < 256 25 인 경우도 있듯이 2개의 string을 이어 붙혔을 때 직접 대소 비교를 해보아야합니다.

 

알고리즘은 다음과 같습니다.

1. 입력으로 들어온 애들을 sort 하여 가장 큰 수를 n-k개 추가한다.

2. 배열의 두 수를 이어붙힌 결과를 직접 비교하여 정렬시킨다. (50개 밖에 되지 않아 간단히 버블소트로 처리하였습니다.)

 

코드는 다음과 같습니다.