[프로그래머스 | 2단계] 가장 큰 수(백트랙킹)

문제 설명

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

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

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

제한 사항

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

입출력 예numbersreturn

[6, 10, 2]	"6210"
[3, 30, 34, 5, 9]	"9534330"

 

풀이

 - DFS 방식으로 푸니까 시간초과

def DFS(numbers, L, result, visite) :
    if L == len(numbers) :
        return "".join(result).lstrip("0")
    else :
        max = ""
        for i in range(len(numbers)) :
            if visite[i] == 0 :
                visite[i] = 1
                result.append(numbers[i])
                num = DFS(numbers, L+1, result, visite)
                if len(num) < len(max) :
                    continue
                if len(num) > len(max) or num > max :
                    max = num
                result.pop()
                visite[i] = 0
        return max
    
def solution(numbers):
    result = []
    visite = [0] * len(numbers)
    nums = []
    for number in numbers:
        nums.append(str(number))
    return DFS(nums, 0, result, visite)