프로그래머스 - 가장 큰 수

프로그래머스 정렬 알고리즘 문제를 풀다가, 정렬 알고리즘을 비롯한 여러 기본 개념들을 알게 되어 블로그를 쓰게 되었다.

문제

간단하게 설명하자면 리스트로 주어진 각 숫자들을 이어 붙여서 가장 큰 숫자를 만드는 것이다.

예시) [3, 30, 34, 5, 9] -> [“9534330”]

풀이

def solution(numbers):
    if not any(numbers):
        return '0'
    str_numbers = list(map(str, numbers))
    digit_converted_numbers = sorted(str_numbers, key=lambda x: x*3, reverse=True)
    return ''.join(digit_converted_numbers)

나는 자리수가 3자리인 것에서 힌트를 얻어, 모든 숫자의 자리수를 맞춰주면서 비교를 하는 방법을 생각해보았다. string으로 바꾸면 앞 자리가 다르거나 자리수가 똑같으면 비교가 가능하다. 그런데 뒤에 0을 붙여서 비교하려고 보니, [3, 30]와 같은 숫자가 문제였다. 결국 검색을 통해 문자열로 바꾼 숫자를 3번 반복해서 자리수를 맞춰주는 방법을 알게 되었다.

아스키 코드

python에서 문자열의 대소 구분을 할 때, 아스키 숫자로 변환되어 맨 앞 문자부터 비교한다. ord 함수를 쓰면 아스키 코드 값을 구할 수 있는데, 인자는 길이가 1인 문자 하나만 넣을 수 있다.

아스키 코드의 값은 0-9, a-Z 순으로 코드 값이 증가한다.

```python
>> ord('1') # 49
>> ord('2') # 50

>> ord('a') # 97
>> ord('b') # 98

>> ord(1)
TypeError: ord() expected string of length 1, but int found

이렇게 문자열을 비교하게 되면 다음과 같이 아스키 코드 값을 첫 번째 인덱스부터 차례대로 비교하게 된다.

추가 설명

앞자리가 다르거나 자릿수가 똑같으면 반복해도, 반복하지 않아도 아스키 코드를 통해 비교가 가능
문제는 앞자리가 같고 자리수가 다른 경우의 비교
*3을 통해 자리수가 같아지도록 반복을 사용하는 이유가 앞자리가 같은 값 간의 비교를 위함

기존 값       반복          결과
3, 331 -> 333, 331 -> 3331 > 3313
3, 30 -> 33, 30 -> 330 > 303

위 예시처럼 숫자를 반복하면 앞자리가 동일한 두 숫자의 순서가 바뀌었을 때 어떤 값이 큰지 파악이 가능하다.
*3을 통해 세 자리수 까지의 모든 숫자가 비교가 가능해진다. 하지만 한 자리수와 두자리 수를 비교하면, 두 번째 비교에서 이미 끝나는 것을 알 수 있다.
만약 1000 이상의 숫자까지 지문에서 허용할 경우, 맞춰줘야 할 자릿수는 * 4가 되어야 올바른 비교가 가능하다.

다른 풀이

from functools import cmp_to_key

def compare(num1, num2):
    if (num1+num2) > (num2+num1):
        return 1
    else:
        return -1

def solution(numbers):
    if all(number == 0 for number in numbers):
        return '0'
    str_numbers = list(map(str, numbers))
    sorted_numbers = sorted(str_numbers, key=cmp_to_key(compare), reverse=True)
    return ''.join(sorted_numbers)

검색했을 때 내 풀이 방식처럼 자릿수를 맞춰주는 것과, 위 풀이처럼 key 함수를 만들어주는 두 방법이 있었다.

sorted

list를 정렬하는 방법은 list.sort()와 sorted(list) 두 가지가 있다. sort()는 list에만 사용할 있고, sorted는 모든 iterable이 가능하다. cmp_to_key에 대해서 알아보기 전에 sorted 함수에서 key 옵션을 어떻게 사용하는지를 찾아봤다.

how-to

파이썬 공식 문서의 정렬 how to 를 보면 sorted 함수에서 key 인자를 사용하는 예시가 다음과 같이 설명되어 있다.

key 파라미터에는 인자를 하나만 받는 function 또는 callable이 들어가야 한다.
정렬에 사용될 key를 반환한다.
input 별로 한 번씩만 호출되기 때문에 빠르다.

# 예시 1
sorted("This is a test string from Andrew".split(), key=str.lower)

# result: ['a', 'Andrew', 'from', 'is', 'string', 'test', 'This']

# 예시 2
student_tuples = [
    ('john', 'A', 15),
    ('jane', 'B', 12),
    ('dave', 'B', 10),
  ]

sorted(student_tuples, key=lambda student: student[2])

# result: [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

cmp_to_key

동작 방식

풀이를 보면 다 cmp_to_key를 사용하는데, 도대체 cmp가 무엇인지, 무엇의 약자인지 궁금해서 찾아봤다. 일단 뭐의 약자인지는 아무리 검색해도 안 나온다…😑 cmp()는 두 개의 값을 비교해서 -1, 0, 1를 int로 반환하는 함수인데, 파이썬 2.x에서는 내장 함수로 있었는데, 3부터는 동작하지 않는다고 한다.

공식 문서

파이썬 공식 문서다음과 같이 설명되어 있다.

비교 함수는 두 개의 인자를 받아들이고, 그들을 비교하여, 작으면 음수, 같으면 0, 크면 양수를 반환하는 콜러블입니다. 키 함수는 하나의 인자를 받아들이고 정렬 키로 사용할 다른 값을 반환하는 콜러블입니다. 구식 비교 함수를 키 함수로 변환합니다.

위에서 구식 비교 함수를 키 함수로 변환한다고 나와있는데, 구식 비교 함수가 cmp()를 말하는 것으로 보인다. 키 함수는 공식 문서에 아래 내용으로 설명되어 있다.

키 함수

키 함수는 sorting, ordering에 사용되는 값을 돌려준다. 요소들을 순서대로 정렬하고 묶기 위해서 아래 함수들이 키 함수를 받는다.

min(), max()
sorted(), list.sort()
heapq.merge(), heapq.nsmallest(), heapq.nlargest()
itertools.groupby()

결론

위 내용들을 종합해봤을 때 다음과 같이 정리해볼 수 있을 것 같다.

두 개 숫자를 비교해서 -1, 0, 1을 반환하는 함수 compare를 만든다.
compare 함수를 cmp_to_key를 통해 키 함수로 바꿔준다.
sorted 함수는 키 함수에서 반환되는 값을 통해 아이템을 두 개씩 비교하면서 정렬한다.

알게된 것

처음에는 cmp_to_key가 뭘까 궁금해서 시작한 블로그였는데, 결국 sorted 함수 내부 구현을 알게된 것이 얻은 부분인 것 같다.

sorted는 삽입 정렬과 병합 정렬을 결합하여 만든 정렬 알고리즘인 팀 정렬로 구현이 되어있다.
정렬 시 두 개의 아이템을 비교하기 때문에 key 함수에서 두 개의 아이템을 비교해 우선 순위를 리턴하게 된다.

정렬을 할 때 reverse 옵션만 알고 있었는데, key 옵션에 대해서 조금 더 자세히 알게 되어 좋았다.

NEXT지킬 블로그를 시작하기 전에 알아두면 좋을 것