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

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 합니다.

입출력 예

numbers return

[6, 10, 2] "6210"

[3, 30, 34, 5, 9]    "9534330"

 

문제 해결 방법

 

주어진 값들의 대소비교를 원활하게 하기 위해서, 3배를 취해준뒤, 내림차순으로 정렬하였다. 

중복제거를 위해 집합을 사용했다. 

 

코드 구현

 

def solution(numbers):
    answer = ''
    
    sortedNum = []
    numbers = list(map(str, numbers))
    numbers.sort(reverse=True)
    
    numbers.sort(key=lambda x : x*3, reverse=True)
    numbers = list(map(int, numbers))
    
#     i = len(numbers)-1

#     while 1:
#         if i == 0:
#             break
#         if int(str(numbers[i-1]) + str(numbers[i])) >= int(str(numbers[i]) + str(numbers[i-1])):
#             i -=1
#             continue
#         else:
#             tmp = numbers[i]
#             numbers[i]=numbers[i-1]
#             numbers[i-1]=tmp
        
#         i = len(numbers)-1

    if max(numbers)==0:
        return '0'
    
    numbers = list(map(str, numbers))
            
    answer = ''.join(numbers)
    return answer

 

# 사실 주석처리 한 부분처럼 구현하려 했으나, 쓸모없어졌다. 

 

시간/공간 복잡도

 

O(n)

 

최적화 및 개선

 

하지않음 

 

어려웠던 점

 

진짜 볼때마다 아주 놀라운 문제다 싶다. 

숫자의 대소비교를 할때, 문자열로 형태를 변환한 뒤,  제한사항에서 주어진 값의 값의 범위를 참고하여 값을 임의로 부풀려 대소비교를 하는 방법을 잊지 말도록 하자.