[BOJ 1422, Python 3] 숫자의 신

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

1422번: 숫자의 신

 

풀이

모든 숫자를 최소 한 번씩 사용하고, 나머지 N - K는 아무거나 사용해서 최댓값을 만들어야 합니다.

 

일단 먼저 모든 숫자를 딱 한 번씩 사용하여 큰 수를 만드는 방법을 생각해보면 최대한 맨 앞에 9가 많이 나오게 해주면 됩니다. 9가 없으면 8, 8이 없으면 7, ...이렇게요

그러면 이제 정렬을 해야 하는데, 정렬하는 방법은 의외로 매우 간단합니다. 숫자 문자열 x, y가 있으면 int(x + y)가 더 큰지, int(y + x)가 큰지 비교하면 됩니다.

하지만 이렇게 정렬해보려고 하니까 파이썬 기본 기능에서는 두 원소를 직접 비교하는 방법은 없습니다.

그래서 functions 모듈의 cmp_to_key 함수를 사용해야 합니다. 이 함수는 C++의 compare과 비슷하지만 값이 양수, 0, 음수로 비교할 수 있습니다.

양수면 앞으로 가고, 0이면 그대로, 음수면 뒤로 보내는 것이죠. C++ compare과 비교하면 파이썬에서 양수는 C++의 True와 같고, 파이썬에서의 음수는 C++에서 False와 같습니다.(https://lucky516.tistory.com/4 참조)

 

이렇게 해서 일단 딱 한 번씩만 사용하여 큰 수를 만드는 방법을 알아보았습니다.

 

이제 나머지 N - K번을 사용하는 숫자는 생각해보면 딱 한 개로 결정할 수 있습니다. 입력 받은 숫자중에서 가장 큰 수를 이용하는 것이죠

예를 들면 9, 1, 2, 3이 있으면 9를 N - K번 사용하는 것이 최대이고, 9, 99, 999, 9999이면 제일 긴 9999를 N-K번 사용하는 것이 최댓값이 나옵니다. 그리고 9, 98을 사용하면 98을 사용하는 것이 9를 사용하는 것보다 길이가 두 배나 더 길어지기 때문에 98을 사용하는 것이 좋습니다.

 

정리해보면

1순위 숫자의 길이가 길어야함

2순위 숫자의 길이가 같을 때, 큰 수를 사용해야함

로 따질 수 있습니다.

 

이것 역시 cmp_to_key를 이용하여 정렬을 하여 첫 번째 원소를 가져오면 됩니다.

from functools import cmp_to_key
k, n = map(int, input().split())
arr = sorted([input() for _ in range(k)], key=cmp_to_key(lambda a, b: 1 if int(a+b) < int(b+a) else -1))
long = sorted(arr, key=cmp_to_key(lambda a, b: 1 if len(a) < len(b) else 0 if len(a) == len(b) and int(a+b) < int(b+a) else -1))[0]
ans = []
flag = False
for i in range(k):
    ans.append(arr[i])
    if arr[i] == long and not flag:
        ans.append(arr[i] * (n - k))
        flag = True
print(''.join(ans))