사용자 도구

사이트 도구


ps:problems:boj:1422

숫자의 신

ps
링크acmicpc.net/…
출처BOJ
문제 번호1422
문제명숫자의 신
레벨플래티넘 5
분류

그리디

시간복잡도O(mnlogn)
인풋사이즈n<=1000, m<=10
사용한 언어Python
제출기록32740KB / 100ms
최고기록56ms
해결날짜2021/06/01

풀이

  • 큰 수 만들기의 응용 문제이다.
  • 큰 수 만들기 에서의 핵심은, 숫자들을 늘어놓아서 가장 큰 수를 만들기 위해서는 숫자들을 문자열로 처리해서 정렬하되 비교함수를 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)이 걸린다.

코드

"""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()

토론

댓글을 입력하세요:
T W N T S
 
ps/problems/boj/1422.txt · 마지막으로 수정됨: 2021/06/01 14:38 저자 teferi