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

문제를 정리해보자.

 

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

주어진 정수를 이용해 가장 큰 수를 만들면 된다.

 

처음에는 완전 탐색을 시도했다. 하지만 시간초과로 실패했다.

두 번째에는 DFS를 시도했다. 하지만 구현에 어려움을 겪어 포기했다.

 

 

DFS

 

 

알고 보니 푸는 방법은 간단했다.

먼저 제한 사항을 보자.

 

 

 

 

예를 들어 [8, 883] 있다.

원소의 크기가 0이상 1,000 이하이므로, 각 원소를 문자열로 보고 3을 곱해준다. 

(1,000이 최대여서 4를 곱할 필요가 없다.)

 

[888, 8838838883]

 

주의해야 할 점은 [0, 0, 0, 0] 같은 예이다.

0000이라는 수는 없다. 0으로 출력해야 한다.

 

 

def solution(numbers):
    li = []
    answer = ''

    if not sum(numbers):
        return '0'

    else:
        for x in numbers:
            li.append((str(x) * 3, str(x)))

        li.sort(reverse=True)

        for num in li:
            answer += num[1]

        return answer
    
    
print(solution([6, 10, 2]))