프로그래머스 - 가장 큰 수 / Python

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

코딩테스트 연습 - 가장 큰 수

문제 설명

문제 설명

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

제한 사항

• numbers의 길이는 1 이상 100,000 이하입니다.
• numbers의 원소는 0 이상 1,000 이하입니다.
• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

입출력 예

numbersreturn

[6, 10, 2]	"6210"
[3, 30, 34, 5, 9]	"9534330"

 

---

정답

def solution(numbers):
    answer = ''

    numbers = list(map(str, numbers))

    numbers.sort(reverse=True, key=lambda x: x * 3)

    for n in numbers:
        answer += n
    return str(int(answer))

 

---

풀이

from itertools import permutations


def solution(numbers):
    answer = ''

    p = permutations(numbers)
    for e in p:
        n = ""
        for i in e:
            n += str(i)
        answer = max(answer, n)

    return answer

  처음에는 모든 경우의 수를 조합해서 풀어보았는데, 전부 시간 초과가 났습니다. 그래서 모든 경우의 수를 탐색하는 문제가 아닌 숫자를 높은 순서대로 정렬하는 방식으로 변경했습니다.

 

def solution(numbers):
    answer = ''

    numbers = list(map(str, numbers))

    numbers.sort(reverse=True, key=lambda x: x * 3)

    for n in numbers:
        answer += n
    return str(int(answer))

 모든 경우의 수를 조합하지 않고 (해당 원소 * 3)을 기준으로 정렬했습니다. 

 가장 큰 수를 만들려면 가장 큰 숫자를 앞으로 오도록 정렬해야합니다. 글자를 기준으로 정렬하기 때문에 numbers 배열을 다음의 코드로 문자열 리스트로 만든 뒤 역순 정렬합니다.

numbers = list(map(str, numbers))

numbers.sort(reverse=True, key=lambda x: x * 3)

 수들이 사전순으로 정렬이 되기 때문에, 역순으로 정렬을 해도 큰 수가 앞으로 오는 것이 아닌, 9가 앞으로 오게 됩니다. 그리고 x * 3을 기준으로 정렬하는 이유는 원소의 범위가 0 ~ 1000까지이기 때문입니다. 

 예를 들어 ['3', '30', '34', '5', '9']를 그대로 정렬하게 되면 ['9', '5', '34', '30', '3']가 됩니다. 이를 수로 만들면 9534303이 되는데, 이는 될 수 있는 가장 큰 수인 9534330보다 작습니다. 이렇게 되는 이유는 '30'이 '3'보다 앞에 오기 때문입니다. 원소가 1000을 제외하면 최대 3자리이므로, 이를 해결하기 위해 x * 3을 기준으로 정렬합니다. 쉽게 보기 위해 x * 3이 적용된 리스트를 보자면 다음과 같습니다.

 

['333', '303030', '343434', '555', '999']

 

 이 리스트를 기준으로 원래의 리스트를 정렬하면  ['9', '5', '34', '3', '30']이 되어 원하는 수를 얻을 수 있습니다.