알고리즘 코드카타 103 - 가장 큰 수

https://school.programmers.co.kr/learn/courses/30/lessons/42746?language=python3

프로그래머스

 

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

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

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

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

입출력 예시

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

 

정수로 이루어진 리스트를 조합해서 만들 수 있는 가장 큰 수를  문자로 출력하는 알고리즘이다. 단순하게 생각하면 모든 순열을 구하고 정렬한 후 가장 끝에있는 숫자를 출력하면 된다. 문제는 이 방법은 시간이 너무 오래 걸린다는 것이다.

import itertools

def solution(numbers):
    answer = ''
    numbers = [str(num) for num in numbers]
    perm = itertools.permutations(numbers)
    perm_numbers = []
    
    for p in perm:
        perm_numbers.append(''.join(p))
        
    perm_numbers.sort()
    
    return perm_numbers[-1]

당연한 결과

 

당연하게도 테스트 케이스는 쉽게 통과했지만 성능문제가 발생했다.

 그리고 한동안 여러 방법을 고민해보았다. 사전순 정렬, 첫째/둘째/셋째자리 각각 비교하기, 등등...
하지만 적절한 코드를 알아낼 수 없었고 결국 모범답안을 찾아보게 되었다.

def solution(numbers):
    numbers = list(map(str, numbers))

    numbers.sort(key=lambda x: (x * 4)[:4], reverse=True)

    answer = ''.join(numbers)

    if answer[0] == '0':
        return '0'
    else:
        return answer

짧은 길이로 작성한 것이 인상적인 코드였다. 블럭별로 알아보자.

 

numbers = list(map(str, numbers))

numbers의 원소들을 str타입으로 변환한다.

 

numbers.sort(key=lambda x: (x * 4)[:4], reverse=True)

핵심이 되는 부분으로 각 원소를 4번 반복한 것의 앞 4자리를 비교해서 그 기준으로 내림차순 정렬한다.

x	x * 4	(x * 4)[:4]
3	3333	3333
30	30303030	3030
34	34343434	3434
5	5555	5555
9	9999	9999

 

위의 방법대로 정렬한다면 완벽하게 정리가 가능하다. 내가 떠올렸던 방법중 하나는 각 원소가 두자리거나 한자리일때 맨 앞자리를 더해서 비교해보려는 설명하기도 복잡한 방법이 있었는데 복잡하게 조건을 추가하기 보다는 답안의 예시처럼 전체 부분을 반복하고 슬라이싱 하는 것이 훨씬 직관적으로 이해가 잘 되었다.

 

answer = ''.join(numbers)

정렬된 numbers를 join해서 정답 변수에 입력한다.

 

if answer[0] == '0':
        return '0'
    else:
        return answer

정렬된 수의 가장 앞자리가 0일때(= 모든 숫자가 0일때) 0을 반환하도록 예외처리를 한다.

 

문제의 설명만 보고 가볍게 접근했다가 생각외로 복잡한 풀이방법에 놀랐고 답안의 간결한 예시에 다시한번 놀라게 된 문제였다.