[프로그래머스] 42746번 : 가장 큰 수

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42746

풀이

[프로그래머스] 42746번 : 가장 큰 수 🥈(LEVEL2)
⏰ 걸린 시간 : 31분
시간복잡도 : O(N)

• 알고리즘 유형 : [정렬]
  

✔️ [문제 접근 방법]

0. numbers의 배열을 내림차순 정렬해준다.
1. 이때 정렬 방법으로 lambda를 통해서 string 값인 x를 4번 반복하도록 해주고 비교군은[:4] 까지 비교해 내림차순 정렬한다.
2. 비교군은[:4] 까지 비교하도록하는 이유는 제한사항에 numbers의 원소는 0 이상 1,000 이하이기 때문이다.

✔️ [주의사항]
0. permutations는 시간복잡도가 O(n!) 인 경우는 적합하지 않다!

tmp = list(map(''.join,itertools.permutations(numbers,len(numbers))))

코드(code)

import itertools
def solution(numbers):
    answer = ''
    numbers = list(map(str, numbers))
    numbers.sort(key=lambda x: (x * 4)[:4], reverse=True) 
    # 이 방법은 x를 4번 반복해서 비교 정렬해준다.
    # [:4]이렇게 한 이유는 numbers의 원소는 0 이상 1000이하의 제약 조건을 갖고 있기 때문이다.


    answer = ''.join(numbers)
    if answer[0] == '0':
        answer = '0'

    return str(answer)

회고

permutations(순열)의 경우에 시간복잡도가 O(n!)의 시간복잡도를 갖는 것에 적합하지 않다!

numbers.sort(key=lambda x: (x * 4)[:4], reverse=True) 

이렇게 비교하는 방법은 Idea측면에서 좋다.

• [해당 코드]

  [프로그래머스] 42746 : 가장 큰 수