프로그래머스 Lv2 문제입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42746#

⌛ 시간 초과 (26.7/100 , 대부분 케이스 시간복잡도 개선 실패)

[나의 풀이1]

from collections import deque

def solution(numbers):
    answer = '0'
    
    tmp = numbers
    queue = deque([['',0,[-1]]])
    
    while queue:
    
        v,cnt,hist = queue.popleft()

        if cnt==len(numbers):
            if v>answer:
                answer = v
            continue
        
        for i,x in enumerate(tmp):
            if i not in hist:
                queue.append([v+str(x),cnt+1,hist+[i]])
        
    return  answer

정수 배열(numbers)가 주어지고 이를 조합하였을 때, 가장 큰 수를 도출하는 문제입니다.

먼저, Queue 구조를 활용한 BFS 알고리즘으로 구현하였습니다.

Queue 구조에

['현재까지 조합한 문자열','조합한 문자열 갯수','조합한 문자열 체크리스트']

를 조합할 수 있는 최대로 합칠 수 있는 문자열 갯수(cnt==len(numbers))까지 append하며 모든 케이스를 확인하였습니다.

조합을 마친 케이스의 경우 현재까지의 최댓값(answer)과 비교하여 가장 큰 수를 구하였습니다.

채점 결과 모든 케이스에서 정답을 도출하였지만 시간복잡도를 해결하지 못하였습니다.

[나의 풀이2]

from itertools import permutations

def solution(numbers):
    answer = []

    for nums in permutations(numbers,len(numbers)):
        answer.append("".join([str(num) for num in nums]))

    return  max(answer)

다른 방법으로 순열을 통해 구현해보았지만, 역시 동일하게 시간초과가 발생하여 다른 풀이를 참고하였습니다.

[다른 사람의 풀이]

def solution(numbers):
    numbers = list(map(str, numbers))
    numbers.sort(key=lambda x: x*3, reverse=True)
    return str(int(''.join(numbers)))

문자열 형태로 정렬한 부분이 핵심이였습니다.

입력된 정수 배열(numbers)을 문자열 배열로 변환시키고 1개 자릿수~3개자릿수까지 크기인 요소마다 3번 반복시킨 뒤 정렬하는 아이디어였습니다.

이때 요소를 3번 반복한 이유로는, 문제에서 제시한 요소의 최소길이가 1자릿수이기 때문에 3자리까지 불려주고 비교하기 위함이였습니다.

감사합니다.