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

https://school.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 합니다.

 

 

 

 

 

 

 

 

 

입출력 예

 

 

 

 

 

---

이 문제의 핵심은 어떤 방식으로 정렬을 시켜야 하는가? 이다. 

 

입출력 예 중 첫 번째인 [6, 10, 2] 의 경우 나열을 시키는 것이기 때문에 3! =6 의 개수만큼 나열 하는 것이 가능하다. 저 경우에 나열하게 되면 [6102, 6210, 1062, 1026, 2610, 2106] 와 같은 결과가 나온다. 이 중 가장 큰 수는 6210 이므로 이 값이 return값이 된다.

 

 

 

 

 

 

 

import itertools 

def solution(numbers):
    li = []
    for i in itertools.permutations(numbers):
        i = str(i).replace(',','')
        i = i.replace(' ','')
        li.append(i[1:-1])
        
    return max(li)

가장 먼저 이 문제에 접근한 방식은 순열을 사용하는 것이었다. itertools의 permutations 함수를 사용하여 input으로 들어오는 수들의 조합을 모두 구한 후 그 중 가장 큰 값을 return하도록 코드를 완성했다.

 

문제 없는 코드였지만 아무래도 모든 조합을 다 계산해야했기에 시간 복잡도 적으로 상당히 좋지 않았다. 프로그래머스에서 제출했을 때 역시 효용성 측면에서 가로막혔다.

 

 

 

 

 

 

def solution(numbers):
    answer = ''
    num = list(map(str, numbers))
    #천의 자리로 맞춰주기
    s = sorted(num,key=lambda x: x*3,reverse=True)
    answer += ''.join(s)
    return str(int(answer))

다음으로는 파이썬의 내장 함수인 sorted 함수를 사용하였는데 정렬 기준을 key 파라미터를 사용해 조정하였다. 이 문제의 제한 사항이 numbers의 요소로는 1 이상 1000 이하의 수만 오도록 되어있는데 이를 이용하여 sorted 의 key 함수를 x * 3 을 적용하여 세자리 수로 만들어주었다. 

 

예를 들어 두 번째 입출력 예를 보면 입력값이 [3, 30, 34, 5, 9] 이다. 이 예시 중 3, 30, 34 와 같이 앞의 숫자만 보고는 나열의 기준을 정할 수가 없기 때문에 3 -> 333 / 30 -> 303030 / 34 -> 343434 로 만들어 둘째, 셋째 자리 수 역시 비교해주어 정렬시켰다.

 

또한 입력값이 [0, 0, 0, 0] 와 같이 0만 오게 되면 join함수를 거치고 나오는 값이 0000이 나오게 된다. 이러한 경우를 방지하기 위해 int 함수와 str 함수를 사용하여 0으로 만들어준다.