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

문제

프로그래머스 가장 큰 수

https://school.programmers.co.kr/learn/courses/30/lessons/42746?language=python3

프로그래머스

 

코드

import itertools
def solution(numbers):
    numbers_per = list(itertools.permutations(numbers))
    answer = -1

    for i in range(len(numbers_per)):
        lst = list(numbers_per[i])

        for a in range(len(lst)):
            lst[a] = str(lst[a])

        hapchim = int(''.join(lst))
        answer = max(answer, hapchim)

    return str(answer)

이 코드는 시간초과로 통과하지 못했다.

 

풀이

numbers_per = list(itertools.permutations(numbers))

입력받은 숫자 배열로 만들 수 있는 모든 순열을 만든다

 

for i in range(len(numbers_per)):
    lst = list(numbers_per[i])

    for a in range(len(lst)):
        lst[a] = str(lst[a])

    hapchim = int(''.join(lst))
    answer = max(answer, hapchim)

순열 리스트를 하나씩 뽑아와서 이어붙여 하나의 숫자를 만든다.

순열리스트를 돌며 숫자를 하나씩 만들때마다 대소비교를 하며 최대값을 찾는다.

 

더 나은 코드

def solution(numbers):
    input_list = list(map(str, numbers))

    input_list.sort(key=lambda x: x * 3, reverse=True)
    answer = int(''.join(input_list))
    return str(answer)

 

풀이

input_list = list(map(str, numbers))

입력받은 배열의 원소를 모두 문자형으로 바꾼다.

 

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

key 매개변수를 가지는 sort() 함수는 key 값을 기준으로 오름차순 정렬됟나.

비교하려는 숫자들의 자릿수를 3배 늘린 상태에서 내림차순으로 정렬한다.

자릿수 3배는 아래와 같이 해당 수를 3번 붙이는 과정을 말한다. 

6 ➡️ 666

10 ➡️ 101010

2 ➡️ 222

산술적으로 3배곱이 아닌 자릿수가 3배가 가능한 이유는 전에 원소들을 모두 문자형으로 바꿔줬기 때문에 가능하다.

문제에서 숫자의 최대 크기가 1000 미만이라고 했기에 3번만 붙여도 된다.

입력되는 숫자의 최소길이는 한자리, 최대 길이는 세자리이기 때문이다. 

(만약 문제에서 숫자의 최대 크기가 10000 미만이라고 했다면 4번 붙였을것이다.)

 

answer = int(''.join(input_list))

정렬된 값이 ['0', '0', '0', ...] 이라면 반환값이 0000... 이 될수 있으니 배열을 정수로 바꿔주는 작업을 한다.

이 작업을 하면 정렬된 값이 ['0', '0', '0', ...] 이더라도 answer은 '정수 0' 일것이다.

 

return str(answer)

"정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다."

라는 문제의 제한사항을 맞춘다.

 

새롭게 배운점 / 느낀점

• sort() 함수에 key라는 매개 변수와 그게 무슨 역할을 하는지 알게 되었다. 예전에 문제들을 풀면서 무조건 오름/내림 차순이 아닌 다른 조건을 걸어놓고 정렬하고 싶어서 코드를 길게 다 구현한적이 있는데, 앞으로 안그래도 될것같다.

• 처음에 도저히 문제를 해결 못해서 해결방법을 검색한 결과가 앞서 나온 '더 나은 코드' 이다. 어떻게 저렇게 창의 적인 방법을 생각해 내는지.. 정말 신기하고 존경스럽다!