백준 1422번: 숫자의 신 [Python]

작성일 | In
플래티넘 IV 플래티넘 IV

문제

숫자의 신

풀이

두 자연수 $a$, $b$를 순서대로 이어붙인 것을 $[ab]$라 합시다. 자연수 $[ab]$가 $[ba]$보다 크다면 다른 자연수 $c$에 대해 $[acb]$가 $[bca]$보다 클 것이므로 $a$가 먼저 오도록 정렬하면 됩니다.

이 문제에서는 $K < N$인 경우 자릿수를 늘리는 것이 수를 가장 크게 할 수 있으므로 주어지는 자연수 중 가장 긴 것 중 위의 정렬기준으로 가장 앞서는 수를 $N - K$개 더 뽑아서 넣고 다시 정렬한 뒤 이어붙여 출력하면 됩니다.

$N, M$과 자연수의 길이가 충분히 작으므로 비효율적으로 구현해도 정답을 받을 수 있습니다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
from functools import cmp_to_key

K, N = map(int, input().split())

nums = [input() for _ in range(K)]

def compare(a: str, b: str):
    ab = int(a + b)
    ba = int(b + a)

    if ab > ba:
        return -1
    elif ab < ba:
        return 1
    else:
        return 0

nums.sort(key=cmp_to_key(compare))
nums.sort(key=lambda x: -len(x))

for _ in range(N - K):
    nums.append(nums[0])

nums.sort(key=cmp_to_key(compare))

ret = ""
for num in nums:
    ret += num

print(int(ret))

백준 1422번: 숫자의 신 [Python]