[🏅5 / 백준 16496 / 파이썬] 큰 수 만들기

 

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

 

풀이

 

여담으로 많은 예외 케이스 때문에 고생을 꽤나 한 문제이다...

 

주어진 수 리스트를 적절히 조합하여 가장 큰 수를 만들어야 한다.

 

큰 수를 만드는 방법은 가장 큰 수를 앞에 배치하면 될 것이라고 생각하기 쉽다.

반만 맞는 말이다. 이 문제에서는 수들의 자릿수가 다를 수도 있기 때문이다.

 

문제에서 수는 1,000,000,000 보다 작거나 같은 음이 아닌 정수라고 했다. 즉, 최대 10자리의 수이다.

따라서 모든 수를 10자리로 맞추어준 뒤에 비교를 해야 한다.

 

자릿수를 맞추는 방법으로 그냥 0을 추가하기, 마지막 수를 더하기, 첫 수를 더하기 등 많은 방법을 시도했지만 모두 AC를 받지 못했다.

사실 AC를 받기도 했었지만, 예외 케이스를 발견해 틀린 것으로 간주하고 요청 게시판에 제보한 뒤 다시 풀었다.

 

마지막으로 시도한 방법이, 현재 수를 10자리가 될 때까지 순서대로 반복해주는 것이었다.

예를 들어 989이면 9899899899, 1234면 1234123412 처럼 말이다.

 

이제 이를 기준으로 내림차순 정렬해준 뒤, 정렬된 순서대로 이어붙인 수를 출력하면 된다.

해당 방법으로 AC를 받을 수 있었고, 발견했던 예외 케이스도 통과했다.

 

import sys
input = sys.stdin.readline

n = int(input())
nums = list(map(int,input().split()))
greedy = []
for i in nums:
    s = str(i)
    leng = len(s)
    while len(s) < 10:
        s += s[len(s)-leng]
    greedy.append(([*list(s)],str(i)))
greedy.sort(key = lambda x : x[0], reverse = True)

ans = ""
for i in greedy:
    ans += i[-1]
print(ans if int(ans) != 0 else 0)

 

 

 

예외 케이스 발견

 

처음으로 백준 문제를 풀며 AC가 아닌데 AC를 받는 예외 케이스를 발견하여 제보했다.

본인에게 여러모로 의미 있는 문제인 것 같다.

 

입력 2 909 9099

출력 9099909