프로그래머스 연습 문제 > 정렬 > 가장 큰 수

문제 설명

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"

---

풀이 방법을 보기 전에 먼저 스스로 생각해보는 것을 추천드립니다.

포인트

1. 수의 비교라기보다는 수의 첫째 자리 수를 비교하는 문제이기 때문에 문자 자료형으로 풀이해야한다.
2. 첫째 자리수를 비교하고, 만약 같다면 다음 위치의 수를 비교하여 더 큰 원소를 택한다. 이 때, 두번째 자리수가 있는 경우와 두번째 자리수가 없는 예외상황이 발생한다.
   (예를들어, [935, 9]의 경우에 9935를 출력하고, [36, 3]의 경우에는 363을 출력해야하기 때문이다.)
 

풀이방법

우선, numbers를 문자형으로 변환한 리스트로 생성해주고, 각 원소를 비교한다.
그 후 아래와 같은 방법으로 원소끼리 비교할 수 있다.

방법1. n1*3과 n2*3끼리 비교하여 더 큰 수를 앞으로 출력
방법2. n1+n2 과 n2+n1을 비교해서 더 큰 수를 출력
(+) 0만 여러개 있는 경우 예외처리

방법1 코드

def solution(numbers):
    numbers = list(map(str, numbers))
    numbers = sorted(numbers, key=lambda x:x*3, reverse=True)
    if numbers[0]=='0':
        return '0'
    else:
        return ''.join(numbers)

필자는 방법1로 풀었습니다.
아래의 방법들은 공부에 참고할 용도로 다른 사람의 풀이를 가져와보았습니다.

방법2 코드

import functools

def comparator(a,b):
    t1 = a+b
    t2 = b+a
    return (int(t1) > int(t2)) - (int(t1) < int(t2)) #  t1이 크다면 1  // t2가 크다면 -1  //  같으면 0

def solution(numbers):
    n = [str(x) for x in numbers]
    n = sorted(n, key=functools.cmp_to_key(comparator),reverse=True)
    answer = str(int(''.join(n)))
    return answer

- functools의 cmp_to_key 함수를 활용하여 정렬
- https://docs.python.org/3/library/functools.html

functools — Higher-order functions and operations on callable objects

cmp_to_key() 함수를 직접 구현한 코드 (참고용)

def cmp_to_key(mycmp):
    
    class K:
        def __init__(self, obj, *args):
            self.obj = obj

        def __lt__(self, other):
            return mycmp(self.obj, other.obj) < 0

        def __gt__(self, other):
            return mycmp(self.obj, other.obj) > 0

        def __eq__(self, other):
            return mycmp(self.obj, other.obj) == 0

        def __le__(self, other):
            return mycmp(self.obj, other.obj) <= 0

        def __ge__(self, other):
            return mycmp(self.obj, other.obj) >= 0

        def __ne__(self, other):
            return mycmp(self.obj, other.obj) != 0
    
    return K