[Programmers] 가장 큰 수 (Python)

가장 큰 수

programmers.co.kr/learn/courses/30/lessons/42746

number 배열이 주어졌을 때 원소 조합으로 가장 큰 숫자를 만들어 리턴하는 문제다.

 

비슷한 문제 / 풀이가 Geeks for Geeks 에 있다.  2가지 풀이 방법이 있는데

 

첫 번째는 숫자를 문자열로 바꾸는 custom compare 함수를 구현하여 언어에서 제공하는 정렬 함수를 사용하는 것이다.

두 번째는 가장 큰 숫자의 자릿 수 만큼 모든 숫자를 만든 다음에, 새롭게 만든 그 숫자들로 정렬하는 것이다.

 

Custom compare 함수 만들어 풀이

www.geeksforgeeks.org/given-an-array-of-numbers-arrange-the-numbers-to-form-the-biggest-number/

import functools


def comp(n1, n2):
    if int(str(n1) + str(n2)) < int(str(n2) + str(n1)):
        return 1
    elif int(str(n1) + str(n2)) > int(str(n2) + str(n1)):
        return -1
    return 0


def solution(numbers):
    numbers.sort(key=functools.cmp_to_key(comp))

    return "".join(str(_) for _ in numbers) if numbers[0] != 0 else "0"

compare 함수를 따로 만들고 해당 함수로 정렬을 한다. python3 로 풀었지만, 다른 언어로 풀어도 비슷할 것이다.

 

한 가지 엣지 포인트는 0 으로만 된 문자열일 경우 정답은 "0" 으로 리턴해야 한다는 것이다. (나도 여기서 틀렸는데 이게 프로그래머스 11번 케이스다. [0, 0, 0, 0] 과 같을 경우 "0" 으로 나와야 한다.)

 

 숫자를 가장 큰 수의 자릿수 만큼 반복하여 정렬하는 풀이

www.geeksforgeeks.org/arrange-given-numbers-form-biggest-number-set-2/

 

가장 큰 수의 자릿수 만큼 숫자들을 반복하게 하고 (예를 들면 [9, 10, 2] 라고 했을 때 [99, 10, 22] 로 만든다는 의미) 그 값들로 정렬하여 문자열로 만드는 것이다. (실제로 풀이에선 가장 큰 수의 자릿수 + 1 만큼 반복하였다.)

 

알고리즘을 (당연하게도) 바로 떠올린 것은 아니고 GFG 에 있는 그림을 보고 아 이렇게 할 수도 있는거구나! 해서 구현하였다. (세상에 천재들이 많다 ㅠㅠ)

def solution(numbers):

    new_numbers = []
    
    max_num = max(numbers)
    size = len(str(max_num)) + 1
   
    for num in numbers:
        new_numbers.append((num, str(num) * size))

    new_numbers.sort(reverse=True, key=lambda x: x[1])
    answer = []
    for nt in new_numbers:
        answer.append(str(nt[0]))

    return "".join(answer) if answer[0] != "0" else "0"

new_numbers 에는 원래 값 num 과 새로 만든 값 (size+1 만큼 반복한 문자열 num) 을 넣었고, 정렬할 때는 문자열로 만든 값을 사용하고 정답을 만들 때는 num 을 썼다.

 

문자열 str(num) 을 만들 때 (size + 1) 을 곱하는 이유는 151, 15 와 같은 값이 있을 때 size (3) 만큼 반복하게 되면 151, 151 이 나온다.

이럴 경우 문자열로 정렬하게 되면 151, 151 은 같기 때문에, 정답이 15115 가 나올 수도 있다. (실제 정답은 15151 이다.)

 

이 때문에 아마 다른 답변을 살펴보면 +1 만큼 반복하게 만든 것이 꽤 있을 것이다.

 

풀고 난 다음에, 프로그래머스 정답을 맞추게 되면 다른 사람 풀이도 볼 수 있는데 제일 투표(?) 많이 받은 답이 바로 이거다. (진짜 짧다! 와우)

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

이게 결국 GFG Hard 풀이인, 숫자 자릿수 만큼 반복(*3) 해서 만들어 정렬 하는 답이다.

 

내 풀이와 다른 점은

 

1. 문제에서 number 가 1000 이하이기 때문에 일괄로 3을 곱한 것이고

 

2. 나는 new_numbers 에 튜플을 넣어서 사용해서 좀 복잡해졌는데, 저 풀이는 정렬의 키에서만 문자 반복을 사용했기 때문에 numbers 를 그대로 써도 되었다는 것이다.

 

그래서 프로그래머스 답변을 참고해서 바꿔보면 이렇게 바꿀수도 있었다. (최종_진짜_최종_최종)

def solution(numbers):
    max_num = max(numbers)
    size = len(str(max_num)) + 1
    snums = []
    for num in numbers:
        snums.append(str(num))

    snums.sort(reverse=True, key=lambda x: x * size)
    return "".join(snums) if snums[0] != "0" else "0"

 

참고로 프로그래머스가 정답 셋이 적어서 GFG (practice.geeksforgeeks.org/problems/largest-number-formed-from-an-array1117/1) 에서도 풀이를 제출해보는 것을 권장한다.