[정렬] 가장 큰 수 (예외 케이스 및 코드)

문제

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

코딩테스트 연습 - 가장 큰 수

 

테스트 케이스

Parameters	Return
[6, 10, 2]	"6210"
[3, 30, 34, 5, 9]	"9534330"
[121, 12]	"12121"
[0, 0, 0]	"0"
[51, 15]	"5115"

여기서 가장 중요한 케이스는 마지막 [51,15]였다. 

 

풀이 

1. Brute Force

가장 간단하게 생각해보면 모든 조합을 만들어서 그 중 가장 큰 수를 답으로 내면 된다.

    answer = ""
    l = map(int, list(map(''.join, itertools.permutations(map(str, numbers)))))
    answer = max(l)
    return str(answer)

이렇게 하면 테스트는 통과하나 제출하면 시간 초과가 뜬다.

 

2. Digit 별 정렬

    numbers = list(map(str, numbers))
    numbers.sort(key = lambda x:x[::-1], reverse=True)
    return str(int(''.join(numbers)))

1번 케스트 케이스였던 [6, 10, 2]가 "6210"이 되어야 한다는 것을 보고 자릿수별로 sorting을 생각해 냈다. 단순하게 첫번째 자리->두번째 자리->...별로 보면서 각 자릿수가 가장 큰 값 순으로 정렬하기로 했다. 자릿수별로 정렬을 하기 위해서는 숫자를 문자열로 치환해서 sorting하는 것이 가장 간단할 것 같았다. 

그러나 이렇게 큰 수대로 정렬하면 30, 3이 있을때 문자열에서는 30이 더 큰 값이라고 인식한다. 따라서 문자열을 lambda x:x[::-1]을 통해 뒤집은 다음에 대소 비교하였다. 그러면 30, 3이 03과 3이 되므로 3이 더 크다고 판단한다.

여기까지는 좋은데, 예외 케이스인 [51, 15]=>"5115"를 통과하지 못 한다. 그 이유는 마지막 digit부터 비교를 하게 되는 데 그러면 "1551"이 결과로 나온다. 즉 이 문제는 digit 별로 정렬해서는 답을 내지 못하는 문제였던 것이다!!

(이런 예외 케이스를 빨리 생각해 내는 것도 라이브 코딩테스트에서는 중요할 것 같다!!)

 

3. 다른 사람 풀이

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

그래서 다른 사람의 풀이를 찾아보니 문자열을 3배로 늘려서 대소비교를 한다. 

하지만 이 풀이를 보지 않고 생각해 낼 수 있을까는 의문이 든다....