[파이썬/알고리즘] 프로그래머스 - 가장 큰 수 (정렬)

[문제]

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

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

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

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

 

[풀이]

def solution(numbers):
    number_star = list(map(str, numbers))
    
    sorted_numbers = sorted(numbers_str, key=lambda x: x*3, reverse=True)
    answer = ''.join(sorted_numbers)

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

 

number_star = list(map(str,numbers))

numbers 안에 있는 숫자를 문자열로 변환한다.

만약 [6, 10, 2]가 들어왔으면 ["6", "10", "2"]로 변환된다.

 

숫자를 문자열로 변환하는 이유는 ASCII 로 정렬하는 것이다.

0부터 9까지의 숫자들은 ASCII 값으로 변환하면 48부터 57까지의 값을 가지게 된다.

예시를 든 2는 ASCII 값이 50이고 6은 54, 10은 1과 0을 따로 보기 때문에 49와 48이다.

ASCII 값은 첫 째자리부터 한 문자씩 이루어지게 된다. 따라서 6이 54로 가장 크고 그 다음은 2가 50이고

10에서 1이 49이기 때문에 가장 마지막으로 정렬된다.

 

즉 숫자로 내림차순 정렬을 한다면 10, 6, 2로 정렬되지만 ASCII 값으로 정렬되면 6, 2, 10으로 정렬된다.

이렇게 정렬이 필요한 이유는 10,6,2를 조합하여 만들 수 있는 가장 큰 수는 6210이다. 그래서 ASCII로 정렬한 것이다.

 

sorted_numbers = sorted(numbers_str, key=lambda x: x*3, reverse=True)

numbers를 정렬하는데 각 문자열을 3번 곱하여서 반환하고 내림차순으로 정렬한다.

 

왜 문자열을 3번 더 써서 반환하냐면 문제에서 원소가 최대 1,000이라고 했기 때문에 세 자리 이상으로 만들기 위해서이다. 

 

예를 들어 3과 31이 있다고 가정하고 조합을 한다면 313 보다는 331이 더 큰 것을 알 수 있다.

하지만 만약 lambda로 변환하지 않고 ASCII로 정렬하면 문자열 첫 번째에서 둘의 ASCII 값은 같다.

문자열 두 번째로 넘어가게 되면 3은 두 번째 자리가 없고 31은 두 번째 자리가 1이고 ASCII 값이 존재하므로 31이 더 큰 문자열로 정렬된다. 즉 31, 3 순서대로 정렬된다는 것이다.

하지만 우리가 원하는 건 3, 31로 정렬되기를 원하기 때문에 lambda을 통해서 값을 세 번 더 써주는 것이다.

그러면 3은 333이 되고 30은 303030이 되는데 두 번째 자리에서 ASCII 값 비교를 할 때 3이 0보다 더 크므로 앞으로 정렬된다. 따라서 우리가 원하는 값을 구할 수 있다.

 

answer = ''.join(sorted_numbers)

리스트를 공백없이 문자열로 만들어준다.

 

if answer[0] == '0':
        return '0'
예외의 경우로 만약 [0,0,0] 이 들어오게 되면 000이 반환되는데 결국 0을 의미하기 때문에 0으로 반환해주는 코드를 추가해준다. 

 

return answer

정답을 반환한다.