[프로그래머스] 가장 큰 수 - python

✏️ 문제설명

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

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

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

⛔️ 제한사항

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

🎈 입출력 예

👩‍💻 내 코드

처음 짠 코드는 주먹구구식이었다.

1. 파이썬 라이브러리 itertools를 이용해 numbers로 만들 수 있는 모든 조합을 구한다.
2. 각 조합의 원소들을 문자들로 바꿔 합친 다음 result 배열에 넣는다.
3. 정렬하여 가장 큰 원소를 뽑아낸다.

from itertools import permutations

def solution(numbers):
    result = []
    permutate_arr = list(permutations(numbers, len(numbers)))
    
    for i in permutate_arr:
        string = ""
        for j in i:
            string += str(j)
        result.append(string)
    
    result.sort(reverse=True)
    return str(result[0])

그 결과 아래와 같이 시간초과가 수두룩하게 일어났다.
물론 예상하고 있었다...코드가 효율적이지 않기 때문에ㅎㅎ

이 문제를 풀면서 가장 중요한 것은 숫자들을 문자열로 바꿔 생각하는 것이라고 생각했다.
파이썬은 특히 문자열을 사전순으로의 정렬이 가능하기 때문이다.
일단 사전순으로 내림차순으로 정렬하면 첫번째 자리가 큰 숫자부터 앞에 올 것이기 때문에 문자열로 변환 후 정렬을 해야겠다고 생각했다.

1. numbers의 원소들을 전부 문자열로 형변환한다.
2. 내림차순으로 정렬한다.

from itertools import permutations
def solution(numbers):
    str_numbers = []
    for i in numbers:
        str_numbers.append(str(i))
    str_numbers.sort(reverse=True)
    string = ""
    for i in str_numbers:
        string += i
    return string
  

이렇게 코드를 짰더니 두번 째 예시를 통과하지 못했다.

두 번째 예시를 해결하기 위해 다른 분들의 코드를 보고 도움을 얻었다...🥲
바로 그냥 정렬하는 것이 아니라 문자열의 상태에서 3배를 한 뒤에 정렬을 하는 것이다.

1. numbers의 원소들을 전부 문자열로 형변환한다.
2. 문자열 상태인 원소들을 3배를 해서 문자 수를 늘린다.
3. 내림차순으로 정렬한다.
4. int로 변환했다가 str로 다시 변환해준다. ([0, 0, 0, 0]인 경우를 생각해서)

from itertools import permutations
def solution(numbers):
    str_numbers = []
    for i in numbers:
        str_numbers.append(str(i))
    str_numbers.sort(key = lambda x : x*3, reverse=True)
    string = ""
    for i in str_numbers:
        string += i
    return str(int(string))

문자열을 배수를 해서 생각해야 했던 것이 생각보다 까다로웠던 것 같다.
이번에 문제를 풀면서 배웠으니까 앞으로는 비슷한 문제가 나오면 잘 풀 수 있겠지?