프로그래머스 가장 큰 수

Johnywhisky·2021년 10월 6일

가장 큰 수

문제 설명

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"

1st solution

def solution(numbers):
    if not any(numbers):
        return "0"
    
    numbers = [str(num) for num in numbers]
    # numbers = list(map(str, numbers))
    # functional programming 방식이지만 comprehension 방식 보다 소요시간이 길다.
    numbers.sort(key = lambda x : x * 3, reverse = True)
    
    return "".join(numbers)

첫 번째 풀이 방법은 수학적 해결 방안이다. list의 숫자 비교 시 자리수를 통합하기 위해 3을 곱해 sorting한다.

Focus Point

내장함수 any
내장 함수 any는 iterable한 객체 요소에 하나라도 Trusy한 값이 있다면 True(boolean 값)를 반환해 주는 함수이다. 이 문제에서는 numbers의 요소로 모두 0이 들어올 경우 함수 return 값으로 0을 주기 위해 사용되었다.

if not any(numbers):

# same w/
def any(iterable_obj) -> bool:
    for element in iterable_obj:
        if element:
            return True
        return False

x * 3의 이유
x * 3수학적 풀이법인 이유이자 핵심이다. 굳이 3인 이유는 1000이하의 수라는 제한 사항이 있기 때문이다.
예를 들어 설명해보자. 첫번째 예시로 5와 54를 조합해 나올 수 있는 수는 554와 545이고 이 중 가장 큰 수는 554이다. 두번째로는 6과 68을 비교해 조합할 수 있는 수는 686과 668이고 둘 중 큰 수는 686이다. 두 경우 모두 같은 두 숫자의 합(55 또는 66)과 둘 중 자릿수가 큰 수(54와 68)를 비교하는 것과 같은 상황이 된다. 즉, 자리수와 상관없이 모두 동일한 사이즈로 키워주고 비교하면 되는 것이다.
이 때, x * 3을 하여 자릿수를 늘린 수를 비교해보면 555 vs 545454가 된다. 이 두 숫자는 str형태로 비교되어 아스키코드의 크기에 따라 555가 앞으로 오게 된다.

key = lambda x : x * 3

2nd solution

python code

from functools import cmp_to_key

def compare_nums(num1: str, num2: str) -> int:
    
    compare1 = (num2 + num1) > (num1 + num2)
    compare2 = (num2 + num1) < (num1 + num2)
    
    return compare1 - compare2

def solution(numbers: list) -> str:
    if not any(numbers):
        return "0"
    
    numbers = [str(num) for num in numbers]
    numbers.sort(key = cmp_to_key(compare_nums))
            
    
    return "".join(numbers)

javascript code

const solution = function(numbers) {

    let str_numbers = numbers.map((num) => num.toString())
    let sorted_numbers = str_numbers.sort((n1, n2) => (n2 + n1) - (n1 + n2))
    
    let answer = sorted_numbers.join("")

    return answer[0] === "0" ? "0" : answer
}

많은 사람들이 사용한 방법을 내 스타일로 다시 풀어보았다. 개인적으로는 이 방법이 1번 풀이보다 출제된 의도에 더 부합한 해결방법인 것 같다. 또한 제한 사항과 상관없이 주어진 문제를 해결할 수 있는 코드이기도 하고, 내장 모듈인 functools와 customize된 비교 함수를 작성 해 인접한 두 수의 합을 비교해 소팅하는 형식으로 이루어져 있다.

예외 처리

numbers의 모든 요소가 0일 때 리턴 값이 0이어야 하기 때문에 예외 처리 코드를 넣어놓았다. python의 경우에는 any함수를 사용해 미리 처리될 수 있게 하였고 javascript에서는 삼항연산자를 이용해 처리했다.

새로 알게된 것

boolean값인 True와 False끼리 연산이 된다는 사실을 처음 알 수 있었다. compare1 - compare2은 결국 True - False, False - True 또는 False - False인데 세 경우 각각 1, -1, 0으로 반환된다. 이건 나중에도 요긴하게 쓸 수 있을 것 같다.

print(True - False) # 1
print(False - True) # -1
print(True - True) # 0
print(False - False) # 0
print(True + True) # 2
print(False + False) # 0

Python 코드 소요시간 비교

방법 1	방법 2

두 방법의 소요시간은 확연한 차이가 난다. 내장 모듈을 활용하여 계산한 결과가 더 오래걸리는 것을 확인할 수 있었다.

여담

1줄 코딩 해결 방법

def solution(numbers):
    return str(int("".join(sorted([str(num) for num in numbers], key = lambda x : x * 3, reverse = True))))

const solution = function(numbers) {
    
    return numbers.map((num) => num.toString()).sort((a, b) => (b + a) - (a + b)).join("")[0] === "0" ? "0" : numbers.map((num) => num.toString()).sort((a, b) => (b + a) - (a + b)).join("")
}