사용자 도구

사이트 도구


ps:problems:programmers:42746

가장 큰 수

ps
링크programmers.co.kr/…
출처프로그래머스
문제 번호42746
문제명가장 큰 수
레벨Level 2
분류

그리디

시간복잡도O((m^2)*nlogn)
인풋사이즈m<=4, n<=100,000
사용한 언어Python
해결날짜2021/05/18
태그

고득점 Kit - 정렬

풀이

  • BOJ의 큰 수 만들기과 동일한 문제. 거기에서는 무려 플래티넘 난이도로 책정되어있다. 풀이는 그쪽 링크를 참고.
  • BOJ문제와 다른점은 숫자 크기가 1000 이하라는 점. 그래서 문자열을 그냥 4번 반복시켜서 만든 문자열을 비교 기준으로 잡는 처리도 별 문제 없이 처리된다.
  • 이렇게 할 경우, 문자열의 최대 길이는 O(m^2) 이므로 비교연산의 시간복잡도도 O(m^2). 따라서 전체 정렬에는 O(m^2nlogn)이 걸린다.

코드

"""Solution code for "Programmers 42746. 가장 큰 수".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/42746
- Solution link: http://www.teferi.net/ps/problems/programmers/42746
"""


def solution(numbers):
    nums = [str(x) for x in numbers]
    sorted_nums = sorted(nums, key=lambda x: x * 4, reverse=True)
    max_num = ''.join(x for x in sorted_nums).lstrip('0')
    return max_num or '0'

토론

댓글을 입력하세요:
E R I R G
 
ps/problems/programmers/42746.txt · 마지막으로 수정됨: 2021/05/28 04:49 저자 teferi