프로그래머스 - 가장 큰 수

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42746

프로그래머스

 

풀이

def solution(numbers):
    numbers = list(map(str,numbers))
    
    numbers.sort(key=lambda x:x*3, reverse = True)
    
    return str(int(''.join(numbers)))

 

 

• 일반적인 방법으로는 풀기가 힘들다.. 내림차순의 방법으로 푼다고 생각하면 [3,30,34]가 있을 때, [34,30,3] 순서로 정렬되지만 실제 답은 34303이 아닌 34330 이기 때문이다.
• 그래서 해당 문제를 해결하기 위해서는 x를 3번 반복한다. 3번 반복의 이유는 숫자가 1000이하여서 3번 반복하면 자릿수가 맞춰진다.
• 파이썬은 string에서 정렬할 때, 첫번째 자리수 부터 진행하며 체크한다. 202와 2는 202가 더 큰 수 202 32의 경우 32가 더 큰 수이다. (첫번째 2와 3의 비교에서 3이 더 큼) 그렇기 때문에 343434 303030 333 이런식으로 자릿수를 맞춰주면 34, 3, 30 이런 식으로 정렬이 가능해지며 답이 된다.
• 그리고 마지막 부분에서 int로 바꿔주고 다시 str로 변경하는데 이는 000과 같은 숫자가 나오는 것을 방지하기 위함이다. (000 -> 0이 되어야 한다.)
• 파이썬에서 문자를 비교하는 원리를 잘 생각해봐야 풀 수 있었다.

 

+ 다른 풀이

from functools import cmp_to_key

def compare(x, y):
    if x+y > y+x:
    	return -1
    elif x+y == y+x:
    	return 0
    else:
    	return 1
    
def solution(numbers):
    numbers = list(map(str,numbers))
    
    numbers = sorted(numbers, key=cmp_to_key(compare))
    
    return str(int(''.join(numbers)))

• 이런식으로 cmp_to_key라는 것을 사용할 수 있다. 함수에서 나온 값으로 정렬하는 건데 양수면 자리를 바꾸고 음수면 바꾸지 않는다.
• 위 예시인 [30,34,3] 문제에서 compare함수를 거치면 3034 < 3430 이므로 [34,30,3] 으로 정렬되고, 303 < 330 이므로 [34,3,30] 으로 정렬된다.
• 생각해보니 해당 방법으로도 정렬이 가능할 것 같다.