[Lv2.] 정렬 - 가장 큰 수

✅ Solution

from itertools import permutations

def solution(numbers):
    ans = []
    numbers = list(map(str, numbers))
    ans = sorted(list(map(''.join, permutations(numbers, len(numbers)))))
    
    return ans[-1]

 

👉 시간 초과 발생❗️

: 굳이 순열이 아니더라도 문제의 예시들을 잘 보고 규칙을 확인한 뒤, 그에 맞게 정렬만 잘 수행해주고 이어 붙여도 풀이 가능❗️

 

def solution(numbers):
    numbers = list(map(str, numbers))
    numbers.sort(key=lambda x:x*3, reverse=True)
    if numbers.count('0') == len(numbers):
        return '0'
    return ''.join(numbers)

 

👉 최종 답안 코드

 

👉 문제 설명 및 제한 사항

• 매개변수 : 0 또는 양의 정수가 담긴 배열 numbers
  • 1 <= 길이 <= 100,000
  • 0 <= 원소 <= 1,000
• 리턴값 : 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로  바꾸어 리턴
  • 정답이 너무 클 수 있기 때문에 문자열로 바꾸어 리턴한다.
• (EX)
  • 매개변수 : [6, 10, 2]
  • 순서 재배치를 통해 만들 수 있는 수 : [6102, 6210, 1062, 1026, 2610, 2106]
  • 가장 큰 수 : 6210

👉 아이디어

• 처음 생각한 아이디어
  • 순열 을 사용하여 주어진 숫자들로 만들 수 있는 모든 수 를 리스트 에 저장한다.
  • 리스트를 오름차순 정렬 한 후, [-1] 를 이용하여 맨 끝 원소를 리턴한다.
  • numbers의 길이가 최대 100,000이므로 순열을 통해 모든 가능한 수를 다 구하면, 최대 100,000*99,999*99,998*...*2*1개의 조합이 생성된다. 따라서 해당 리스트를 정렬하려면 시간 복잡도가 어마무시하게 커지며 시간 초과가 발생한다.
• 여러 풀이를 참고하여 푼 방법
  • numbers의 원소를 str으로 바꾼 후, 다르게 설정한 정렬 기준을 key로 설정하여 정렬한다.
    
    • 2번째 예제를 보면 3, 30, 34가 34, 3, 30 순 으로 정렬이 되어야 하는데 사전순으로 내림차순 정렬을 하면 34, 30, 3 순으로 정렬된다.
    • 자릿수를 맞춰 비교하는데, 뒤에 0을 붙여 맞추면 내림차순 정렬한 결과는 똑같다.
    • 이를 해결하기 위한 방법으로 숫자들을 3번씩 반복 한 후, 세자리 수 까지 잘라서 비교한다. (원소는 최대 1,000이므로❗️)
    • [3, 30, 34] > [333, 303030, 343434] > [333, 303, 343] 으로 내림차순 정렬한 결과는 [343, 333, 303] 이 된다.
    • 원래 숫자로 바꿔주면 [34, 3, 30] 순서가 되어 문제에서 요구하는 가장 큰 수를 구할 수 있다. 
    • 숫자를 반복시키는 이유는 앞에서부터 같은 숫자패턴이 존재하는 숫자들의 비교를 위해서이다. 기존 숫자를 반복시키게 되면 그 숫자가 앞에 왔을 때 만들 수 있는 최대 숫자를 만들 수 있다. (비교 가능한 범위까지)
  • 만약, numbers 리스트에 원소가 0밖에 없다면 '000'이 나올 수 있으므로 조건문을 통해 '0'을 리턴 하도록 해준다.
  • ''.join()으로 결과 리스트를 문자열로 묶어 리턴한다.

참고하며 알게된 내용

 

✅ 다른 사람 풀이 참고

def solution(numbers):
    numbers = list(map(str, numbers))
    numbers.sort(key=lambda x: x*3, reverse=True)
    return str(int(''.join(numbers)))

 

👉 깨달은 것 / 알게된 것

• 조건문을 사용하지 않고 int 변환 후, 다시 str으로 변환 하면 '000'을 '0'으로 리턴할 수 있다.
  • BUT, str(int())가 필요없는 테스트케이스에도 적용이 되어 시간복잡도가 높아지므로 조건문을 사용하는게 좋다.
  • 0의 개수와 numbers의 길이를 비교하는 방법말고도 numbers의 sum이 0인지를 통해 조건문을 작성할 수 있다.