[프로그래머스] 가장 큰 수

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

코딩테스트 연습 - 가장 큰 수

 

파이썬의 강력함을 몸소 느낄 수 있는 문제였다. 단 3줄만으로 문제를 풀 수 있었다.

 

처음에는 모든 경우의 수를 구해 가장 큰 값을 구하는 방법으로 접근해 permutations를 이용했다.

허나 이 방법을 이용하면, O(N!)의 시간복잡도를 가져 절대 통과할 수가 없었다...

 

그럼 어떻게 풀어야 할까? 필자 또한 문제를 풀다 도저히 풀이법이 떠오르지 않아 웹 포스팅을 참고했다.

 

이 문제를 풀기 위해서는 먼저 리스트 각 요소의 맨 앞자리 수를 고려해야 한다. 이를 위해 첫 번째로 파이썬의 문자열 정렬에 대해 이해할 필요가 있었다.

 

파이썬에서는 숫자로 된 문자열을 정렬할 때, 맨 앞자리부터 비교해 숫자가 더 크면 더 큰 문자열 순서로 정렬해준다.

 

11과 9를 비교할 때, 11이 크기는 더 크지만 맨 앞자리 수는 9가 더 크므로 정답을 얻기 위해서는 9가 앞으로 와야 한다.

 

이를 문자열로 변환해 비교해주면, 맨 앞자리부터 비교해 '9'의 9 가 '11'의 1보다 크기 때문에 '9' 가 '11'보다 큰 순서로 정렬해준다.

 

만약 '3'과 '30'을 정렬해야 한다면, 문제의 요구에 따라 '303'이 아닌 '330'이 되어야 하므로 '3'을 '30'보다 더 큰 순서로 정렬해 주어야 하는데, 이를 위해서 각 자리를 3배씩 늘릴 필요가 있다.

 

문자열에 *3을 해주어 '333'과 '303030'을 만들어 주면, 앞에서 두번째 자리에서의 비교를 통해 '333'이 '303030'보다 더 큰 문자열로 정렬해 줄 수 있다.

 

그리고 두번째로는 파이썬 내장 정렬 메소드인 sort()에 대해서 더 알 필요가 있었다.

 

보통 리스트의 요소를 정렬하기 위해 단순히 .sort()로만 사용하곤 했는데, sort의 내부 키워드인 key를 이용해 리스트의 각 요소에 조건을 걸어 정렬할 수 있고, 기본적으로 오름차순으로 정렬해주는 sort의 결과를 따로 역순으로 만들 필요 없이 reverse 키워드를 이용할 수 있었다.

 

    numbers.sort(key = lambda x : str(x) * 3, reverse = True)

반드시 람다 함수를 사용하여야 하는 것인지는 잘 모르겠는데, 파이썬 공식 문서를 참고하면 람다 함수를 통해 리스트의 요소에 접근하는 듯 해 이를 응용했다. 다른 웹 포스팅을 봐도 람다를 이용한 접근이 바이블 처럼 쓰이는 듯...

student에 비교할 요소를 지정하고, student끼리의 비교를 통해 정렬하는 것으로 보인다... 확실하지는 않다

 

위처럼 식을 쓰면, key 키워드에 람다 함수를 이용해 각 문자열을 3배씩 늘려 비교한 것을 역순으로 정렬하므로 정확히 우리가 원하는 리스트를 결과로 얻을 수 있다.

 

이게 끝이 아니다. 마지막으로 리스트가 [0, 0, 0, 0] 과 같이 모두 0일 때 자리수가 늘어나지 않고 0이 되어야 하는 것을 고려해 문자열로 만들어진 것을 정수로 한번 변환하고, 다시 문자열로 변환해야 한다. 

만약 위처럼 [0, 0, 0, 0]이 입력으로 주어지면 문자열로 변환했을 때 '0000'일 것이고 이는 정수로 그냥 0이다. 따라서 '0'으로 바꿔주기 위해 아래 코드를 추가해야 한다.

str(int("".join(list(map(str, numbers)))))

join은 단순히 문자열끼리 합쳐주기 위한 것이다.

 

 

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