[정렬] 가장 큰 수 (프로그래머스, Level2) - Retry

문제

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

• 주어진 numbers 배열에 있는 숫자들을 이어붙여서 만들 수 있는 숫자 중, 가장 큰 숫자를 return 해라.

풀이

이 문제는 정확한 풀이를 떠올리기 어려웠다. 문제를 읽었을 때 처음 생각이 났던 방법은 permutation(순열)을 통해 조합할 수 있는 모든 경우를 구한 후, 최댓값을 answer로 리턴하는 것이었다. 하지만 이 방법은 시간 초과 에러가 나타날 것으로 생각이 되었고, 실제로 구현을 해보았을 때도 시간 초과가 되어 오답 처리 되었다.

다음 방법으로는 numbers 배열의 각 숫자들의 앞 자리만 비교해서, 앞 자리를 기준으로 정렬하는 것이다. 이 때 숫자를 문자형으로 변환하고, 앞 자리를 슬라이싱하여 lambda 함수를 통해 정렬했는데, 정렬 결과로 숫자를 결합했을 때 최대 숫자가 아니었다. 그 이유는 다음과 같다.

예) numbers 배열에 3과 34가 있는데, 3이 34보다 앞에 온 숫자가 정답이다. 하지만, 실제로 정렬을 했을 때는 34가 3보다 앞에 오는 순서로 리스트에 정렬되었고 따라서 오답이 출력되었다.

따라서 이 방법으로 코드를 구현하니 숫자의 앞 자리가 모두 다른 numbers 배열만 통과하였다.

떠올린 방법들이 모두 오답이어서 다른 풀이를 검색해보았고, 이 문제의 핵심은 문자열의 아스키코드 비교였다. 숫자로 구성된 문자열이었기에 해당 로직을 생각하기가 어려웠다. 이번 문제를 통해 숫자로 구성된 문자열의 아스키코드 비교를 알 수 있게 되었다.

✏️ 추후 보완 예정

코드

정답 코드

✏️ 추후 보완 예정

오답 코드 (순열 사용) - 시간 초과

from itertools import permutations

def solution(numbers):
    answer = ''
    comb = list(permutations(numbers, len(numbers)))
    
    arr = []
    for i in range(len(comb)):
       num = ''
        
       for j in comb[i]:
           num += str(j)
       comb[i] = num
    
    answer = max(comb)
   
    return answer

오답 코드 (숫자의 앞자리를 기준으로 정렬)

• numbers 배열 숫자들이 앞 자리가 모두 다른 경우만 정답 출력

def solution(numbers):
    answer = ''
    
    for i in range(len(numbers)):
        num = str(numbers[i])
        numbers[i] = num
    
    numsort = sorted(numbers, key = lambda x:x[0], reverse=True)
    
    for i in numsort:
        answer += i
   
    return answer

참고

문제풀이 아이디어(1)

문제풀이 아이디어(2)