[알고리즘] 프로그래머스 - 가장 큰 수 - 42746 파이썬 문제 풀이

문제 링크

문제

입출력 예시

조건

풀이 - 순열 (시간 초과)

def solution(numbers):
    ans = []
    def backtrack(cur):
        if len(cur) == len(numbers):
            ans.append(''.join(map(str, cur)))
        
        for num in numbers:
            if num not in cur:
                cur.append(num)
                backtrack(cur)
                cur.pop()
    backtrack([])
    return max(ans)

처음 문제를 계속 생각해봤을 때 숫자로 접근해서 정렬할 경우 예외상황이 너무 많아서 정렬로는 도저히 방법이 떠오르지 않았다. 그래서 시간 초과가 날 것을 알고는 있었지만 완탐을 시도해봤다. 모든 순열의 조합을 구해서 가장 큰 값을 출력 해주는 방법을 시도했는데 역시나 테스트 케이스 정도는 통과하지만 제출했을 때에는 시간초과가 발생했다.

풀이 - 정렬 (문자열 정렬하기)

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

여러 블로그를 찾아봤는데 모두 이 방법으로 풀이가 적혀있었다. 이게 정석적인 풀이인가보다. 이러한 풀이법을 한번도 본적이 없다면 생각할 수 없을 것 같은 문제 풀이 방법이었다.
숫자로 접근하는 것이 아닌 자릿수를 맞춰놓고 문자열로 정렬을 하는 방법이다. 여기서 key에 3을 곱한 이유는 조건에서 1000이하의 숫자만 있다고 했기 때문에 한자리 숫자도 3자리로 만들어 자릿수를 맞춰주기 위함이다.
그리고 처음에는 return을 ''.join(map(str, arr))을 사용했는데 1개의 케이스에서 틀렸다는 결과가 나왔다. 생각을 해보니 조건이 '0 이상'이기 때문에 [0, 0, 0]과 같은 입력이 들어오는 케이스도 있는데 기존에 사용한 방식을 사용하면 '000'이 출력이 되기 때문에 이것을 '0'
으로 단축시켜주기 위해 int로 한번 변환했다가 다시 str로 변환했다.