[그리디] 최대 숫자 만들기

문제링크

https://www.codetree.ai/missions/8/problems/make-biggest-num?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

1. 핵심

• from functools import cmp_to_key 중 custom comparator만들기

# o1 앞, o2 뒤 
# compare의 기본: 오름차순(o1 - o2 < 0: -1) 
# 내림차순!!! (o1 - o2 > 0: -1)
# -1이 있는 if문이 현재의 (오름, 내림)차순을 나타냄.
def compare(o1, o2):
     if o1 - o2 == 0:
         return 0
     if o1 - o2 > 0:
         return 1
     if o1 - o2 < 0:
         return -1
         
def compare(o1, o2):
	# 43, 4일 때 우리가 원하는 배열은 4, 43이다.
    # 5, 54
    # 왜냐하면 434 보다 443이 더 크기 때문이다.
    new_o1 = int(o1 + o2) # 434
    new_o2 = int(o2 + o1) # 443
    # 따라서 현재 배열과 우리과 원하는 배열은 다르다!
    # new_o2가 더 클 때 배열을 변화시켜야하므로 1을 return
    # new_o1이 더 크다는 것은 이미 원하는 배열이라는 것! 554(o1) > 545(o2)
    if new_o1 - new_o2 == 0:
        return 0
    if new_o1 - new_o2 > 0:
        return -1
    if new_o1 - new_o2 < 0:
        return 1

 

2. 코드(Python)

from functools import cmp_to_key

n = int(input())
nums = [input() for _ in range(n)]

def compare(o1, o2):
    # 4 43
    # 443, 434
    new_o1 = o1 + o2
    new_o2 = o2 + o1
    if int(new_o1) - int(new_o2) == 0:
        return 0
    if int(new_o1) - int(new_o2) > 0:
        return -1
    if int(new_o1) - int(new_o2) < 0:
        return 1

nums.sort(key=cmp_to_key(compare))

print(''.join(nums))