Problem

문제 설명

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

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

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

프로그래머스: 가장 큰 수

제한 사항

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

MY SOLUTION

1st 시도: FAIL🧐

우선순위 큐를 이용해서 푸는 건 줄 알았는데 아니었음. 아마 가능은 할 것 같은데 굳이 그렇게 풀 이유는 없는 듯(시간초과)

더 정확하게 말하면, max heap으로 풀었었음. 그런데 아래와 같이 하게 되는 경우 3과 34 중 34를 먼저 선택하지 않고 3을 먼저 선택하게 됨(priority(3) > priority(3,4)) 그래서 오류발생.

import heapq

def try1(numbers):
    heap = []; ans = ''
    for n in numbers:
        heapq.heappush(heap, tuple(map(lambda x: int(x)*-1, str(n))))
    
    while (heap):
        x = list(map(lambda i: str(i*-1), heapq.heappop(heap)))
        ans += reduce(lambda i, j: i+j, x)
        
    return str(int(ans))

2nd 시도: FAIL🧐

[파이썬 알고리즘 인터뷰]에 동일한 문제가 있어서 잠깐 훑고 삽입정렬로 구현했는데,

삽입정렬은 i-1번째 수까지가 지금까지 정렬된 수들,

j = i..1까지 돌면서 j와 j-1번째 수를 크기에 따라 swap해 주는 게 삽입정렬이다.

그런데 이것도... 시간초과가 나서 실패했다 😢

def try2(numbers):
    # 삽입 정렬 구현: 시간 초과
    def needSwap(x, y):
        return str(x) + str(y) > str(y) + str(x)
    for i in range(1, len(numbers)):
        # numbers[i]
        j = i
        while(j>0 and needSwap(numbers[j], numbers[j-1])):
            # numbers[i]가 움직이는 애, numbers[j]와 비교하기
            numbers[j], numbers[j-1] = numbers[j-1], numbers[j]
            j-=1

    return str(int(reduce(lambda x, y: str(x)+str(y), numbers)))

3rd 시도: SUCCESS🥳

결국 구글링해서 찾아보니 functools의 cmp_to_key() 함수를 사용해서 sorted() 함수로 간단하게 구현하면 되는 문제였다. 이렇게 하는 경우 실행 시간도 훨씬 줄어든다.

def solution(numbers):
    ans = [str(i) for i in numbers]
    def comparator(x, y):
        # t1 > t2인 경우 1 반환, t1 < t2인 경우 -1 반환, t1 = t2인 경우 0 반환
        t1 = x+y; t2 = y+x
        return (int(t1)>int(t2)) - (int(t1)<int(t2))
    return str(int(''.join(sorted(ans, key=cmp_to_key(comparator), reverse=True))))

• 이때 comparator 함수에 두 개의 인자 x,y를 넣어서 비교 후

  • x의 우선순위>y의 우선순위: 1 반환(swap X)
    x의 우선순위<y의 우선순위: -1 반환(swap O)
    ****x의 우선순위=y의 우선순위: 0 반환

    그래서 sorted([리스트], key=cmp_to_key(comparator))로 쓸 수 있다.

• 이 경우, 원래 default 정렬 방식인 오름차순 정렬으로 일부러 구현한 후, reverse=True를 통해 내림차순을 구현한 것 같다.