백준[16496] 큰 수 만들기 (Python3)

생각보다 쉬운 문제
파이썬이 아닌 언어로 풀었으면 조금 돌아가야 했을 것이다.

시도한 방법 1

입력된 수들을 가장 긴 자릿수만큼 자신의 일의자리 수를 더해준다.
예를 들어 입력이 432, 9999 가 들어온다면, 4322, 9999로 맞춰준다.
그다음 내림차순 정렬을 해, 원본 수를 이어붙인다.

 

반례로 98, 9888889가 들어오면 98이 먼저 와야 하는데 뒤로 가야 하는 문제가 발생했다.
다른 사람 코드 보는 과정에서 알았는데, 끝자리 수만 추가해주는게 아니라
해당 수를 적당히 이어붙이고, 앞에 10개만 가져와서 비교하면 됐었다.
(10개만 가져오는 이유는, 수의 범위가 10억 이하이기 떄문)

시도한 방법 2

두 수 A, B가 있을 때, AB와 BA의 값을 비교한 다음 위치를 바꾼다.
N의 범위가 매우 작기 때문에 버블정렬을 사용했다.
정렬에 O(N^2)이 소모됐지만 빠른 시간 안에 문제를 해결할 수 있었다.

 

N을 좀 더 늘려도 될거 같은데, 왜 1000으로 했는지 모르겠다.

 

코드

from collections import defaultdict

def main():
    N = int(input())
    nums = list(input().split())
    for i in range(N - 1, 0, -1):
        for j in range(i):
            A = nums[j]
            B = nums[j + 1]
            AB = int(A + B)
            BA = int(B + A)
            if AB < BA:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
    S = "".join(nums)
    if S[:2] == "00":
        print("0")
    else:
        print(S)

if __name__ == "__main__":
    main()