테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 숫자의 신 ======

===== 풀이 =====
  * [[ps:problems:boj:16496]]의 응용 문제이다.
  * [[ps:problems:boj:16496]] 에서의 핵심은, 숫자들을 늘어놓아서 가장 큰 수를 만들기 위해서는 숫자들을 문자열로 처리해서 정렬하되 비교함수를 x+y<y+x 로 놓으면 된다는 것이다.
  * 여기에서는 주어진 K개의 수 + 내가 선택한 N-K개의 수를 늘어놓아서 가장 큰 수를 만들어야 한다. 결과를 가장 크게 만들기 위해서는 N-K개의 수를 선택할때, 최적의 수 한개를 찾아서 N-K번 붙여야 한다. 그리고 최적의 수는, 자릿수가 가장 크고, 자릿수가 동일할경우는 문자열 순서로 가장 큰 수이다 (이말은 결국 그냥 정수형으로 비교했을 때 가장 큰수이다).
  * 그러면 K개의 수 + 최적의 수 N-K개를 늘어놓는 방법은, 위에서 말했듯 비교함수를 지정해서 N개의 수를 정렬하고 이어붙이면 끝.
  * N개의 수를 모두 정렬하는 것이 싫다면, K개의 수를 정렬하고, 정렬된 배열에서 '최적의 수'가 등장하는 위치를 찾아서, 그 바로 뒤에 최적의 수 N-K를 추가해 주면 된다. 
  * 최대 자릿수가 m이라고 하면 비교 연산은 O(m)이니까, n개의 수를 정렬하는 데에는 O(mnlogn)이 걸린다. 

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 1422. 숫자의 신".

- Problem link: https://www.acmicpc.net/problem/1422
- Solution link: http://www.teferi.net/ps/problems/boj/1422
"""

import functools


def main():
    K, N = [int(x) for x in input().split()]
    nums = [input() for _ in range(K)]

    num_to_repeat = max(nums, key=int)
    sorted_nums = sorted(
        nums + [num_to_repeat] * (N - K),
        key=functools.cmp_to_key(lambda x, y: -1 if (x + y) > (y + x) else 1))
    answer = ''.join(sorted_nums)

    print(answer)


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:플래티넘_5}}