백준 16469: 큰 수 만들기 (Python)

문제

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

해설

처음에는 "?? 뭐지 이런게 플래5라고?" 싶을 정도로 단순히 풀릴 것 같은 문제였다.

각 숫자들을 '가장 큰 자릿수'에 맞춘 다음, 정렬시킨 후 원본 값을 불러오면 되는거 아닌가 했던 것이다.

예를 들어,

3 30 34 5 9

 

의 경우

3 30 34 5 9
(자릿수 맞추기)
30 30 34 50 90
(정렬)
90 50 34 30 30
(원본값 불러오기)
9 5 34 3 30

 

로 풀 수 있지 않을까 했던 것이다.

 

 실제로 이렇게 생각을 하고 제출하니 83%까지는 올라가는 듯 했다. 그러나 여지없는 실패.

위 방식으로 코드를 짜면 다음과 같은 반례가 생긴다.

2
1211 121

ANS: 1211211
WA: 1211121

 

문제를 해결하는 핵심은, '두 수를 이어붙여 더 큰 수를 만들 수 있는 방법'을 찾는 것이다.

즉, 두 수 a와 b를 비교할 때, 단순히 수의 크기를 비교하는 것이 아니라 a+b와 b+a를 문자열로 비교하여 더 큰 경우를 선택해야 한다.

int(str(a) + str(b))와 int(str(b) + str(a)) 중 더 큰 걸 선택하기

 

이러한 방식으로 모든 숫자들에 대해 비교를 여러번 진행시켜 숫자를 이어붙이면, 가장 큰 수를 만들 수 있다.

비교를 여러번 진행하는 방식은 버블 정렬과 비슷한 방법이 된다.

버블정렬은 보는 것처럼 앞에서부터 두 수를 비교해서 스왑을 진행해가는 정렬 방식이다.

앞에서 말한 방식대로, [a에 b를 이어붙인 수]와 [b에 a를 이어붙인 숫자] 중 더 큰 숫자가 무엇인지 비교해 스왑을 진행해간다..

그러면 최종적으로 인접한 숫자들끼리 비교가 이루어지고 최종적으로 만들어질 수 있는 가장 큰 숫자가 만들어지게 된다.

 

마지막으로 '수는 0으로 시작하면 안되며, 0이 정답인 경우 0 하나를 출력해야 한다.' 라는 조건을 만족시키기 위해, str 형태의 정답을 int 형으로 변환해주면 된다.

 

 

코드

N = int(input())
arr = list(input().split())

for i in range(N):
    for j in range(N-1):
        a = arr[j] + arr[j+1] 
        b = arr[j+1] + arr[j]
        if a > b:
            continue
        else:
            arr[j], arr[j+1] = arr[j+1], arr[j]

print(int(''.join(arr)))

여담

힌트가 없었으면 못 풀었을 것 같은 문제다.. 구현에 비해 발상이 어려워서 플5인가보다.