[프로그래머스] 가장 큰 수 - 반례 포함

가장 큰 수

프로그래머스

 

def solution(numbers):
    answer = ''
    numbers = list(map(str, numbers))
    numbers.sort(key=lambda x: x*4, reverse=True)
    for num in numbers:
        answer += num
    return str(int(answer))

 

 

두 번째 예시는 아래와 같습니다.

[3, 30, 34, 5, 9]
"9534330"

파이썬 문자열을 큰 순서대로 정렬하면 문자열은 앞자리가 큰 순서대로 정렬되므로 9, 5, 34, 30, 3 이 됩니다. 하지만 3이 30보다 먼저 와야만 합니다. 내림차순 정렬이라면 30이 3보다 큰 숫자이니까 303이 되어 원하는 결과와 달라지게 됩니다. 앞자리 수가 같다면 그 다음 숫자를 비교하도록 해야 합니다. 어떻게 할 수 있을까요? 즉 정렬을 했을 때 이어 붙이면 원하는 조합의 가장 큰 숫자가 될 수 있도록 코드를 작성해야 합니다.

 

 

파이썬의 문자열 정렬은 사전순(lexicographical) 정렬을 하게 되는데, 숫자를 문자열로 변경한다면 왼쪽에서 오른쪽으로 한 글자씩 비교하게 됩니다.

---

Ex) 예시

["cat", "car"]

"c", "a"는 같지만 "t", "r"은 다름 사전 상 "r"이 먼저오기 때문에 정렬하면 ["car", "cat"]

["abc" , "abcd"]

모든 글자가 같고 길이만 다른 경우, 길이가 짧은 문자열이 사전순에서 앞에 오게 됩니다.

["34", "30", "3"]

첫 번째 숫자 3은 모두 같음, 두 번째 숫자는 4, 0인데 숫자 "3"은 두 번째 글자가 없음. 그래서 사전 순서에서 4, 0보다 먼저 오게 되고("a"와 "ab"를 비교하면 "a"가 사전에서 먼저오게 되는 것과 같음) 두 번째 숫자인 4, 0을 서로 비교하면 사전에서 0이 4보다 먼저 나오게 되므로 오름차순 정렬을 하게 되면 ["3", "30", "34"]가 됩니다.

---

 

다시 예시로 돌아와서 숫자 [ 3, 30, 34 ]을 비교하게 되면 34303이 되어버립니다. 우리가 원하는 가장 큰 숫자는 34330인데 알맞지 않습니다. 그래서 문자열 변환이 필요합니다. 문자열로 변환을 해주게 되면 공통된 맨 앞자리 3을 확인한 후 다음 자리를 확인하는 데 "3"은 일의 자리 숫자이므로 비교가 끝나고, "30", "34"가 십의 자리 숫자까지 있으므로 다시 비교를 하게 되어 0보다 4가 크므로 34303가 됩니다.(내림차순)

 

 

결국 나오는 숫자는 같아집니다. 하지만 아직 끝이 아닙니다. 파이썬에서 문자열은 곱하기 연산을 하면 숫자가 문자 취급을 받게되어 옆으로 붙게 됩니다.

 

 

문자에 *3을 하게 되면 [ "333", "303030", "343434" ]가 되는데 이 상태에서 문자열 정렬을 하게 되면 343434가 첫 번재, 333이 두 번째, 303030이 세 번째 순서가 됩니다. 숫자 정렬과의 차이점입니다.

 

 

문자열 곱하기를 한 상태로 정렬을 하면 [ "34", "3", "30" ] 이 되므로 이 숫자들을 붙여주면 34330이 되어 가장 큰 숫자의 조합을 찾을 수 있습니다.

 

 

Q2) 왜 *3인가? *2는 안되는건가?

 

문제의 조건은 여러가지 순서를 조합해서 만들 수 있는 가장 큰 숫자를 만드는 것입니다. 리스트 numbers에 숫자가 x, y 2개가 있다고 하면 (x+y) VS (y+x)를 비교해서 더욱 큰 수를 찾아내는 것입니다. 그런데 *3을 해서 내림차순 정렬을 하면, (x+y) VS (y+x) 비교와 같은 효과를 낼 수 있습니다. 

"*3 이후 문자열 내림차순 정렬" = "모든 조합 비교하여 가장 큰 수 찾기"

[ "3", "34" ] 의 모든 수를 조합하여 비교하면 "3"+"34"="334", "34"+"3"="343" 가 됩니다. "343"가 더 크기 때문에 "34"를 앞에 두어야 합니다. 

문제의 조건에서 0 이상 1000이하라고 했으니 1000이 아니면 최대 3자리 숫자일 겁니다. 파이썬에서 "3", "34"의 단순 사전식 순서 비교는 어려울 수 있으나 곱하기 연산을 통해 길이를 늘려준다면 완전히 같은 숫자가 아닌 경우 반드시 뒤로 갈때 다른 숫자가 나오게 되므로 비교하기가 수월해집니다. 1000이 아니라면 최대 3자리 숫자이기 때문에 1자리인 숫자를 비교하기 위해 최소 3번은 곱해주어서 3자리로 만드는 것이 사전식 비교에 수월하기 때문입니다.

3 > *3 > 333

34 > *3 > 343434

98 > *3 > 989898

9 > *3 > 999

곱해준 후가 비교하기 수월해집니다.

이렇게 정렬해준 후에 그 숫자들을 하나로 묶으면 되기 때문에 for num in numbers:가 마지막에 들어갑니다.

과정은 다르지만 결과는 (x+y) VS (y+x)를 직접 모두 해준 것과 같습니다.

반례)

[8, 89, 887] >>> 반례

이 예제에서 조합해서 나올 수 있는 가장 큰 수는 898887입니다.

*3을 하게 되면 [ "888", "898989", "887887887" ] 입니다. 문자열 내림차순 정렬을 하면 89, 8, 887이 됩니다. 898887은 원하는 숫자입니다.

*2를 하게 되면 [ "88", "8989", "887887" ] 입니다. 문자열 내림차순 정렬을 하면 89, 887, 8이 됩니다.898878은 원하는 숫자가 아닙니다.

 

Q3) return 할 때 int()로 묶어주는 이유

 

 

[ 0, 0, 0 ]과 같은 경우 문자열로 변환한 뒤 코드를 실행하면 "000"이 되는데, 숫자 000은 그냥 0이기 때문에 int()로 묶어서 0으로 만들어 주어야 합니다.