프로그래머스 가장 큰 수 파이썬

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

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

 

이문제는 정말이지.. ㅎㅎㅎ

그다지 어렵지 않은 인상을 주며 나를 아주 큰 곤경에 빠트린 문제다.

 

5시간 넘게 고민하다가 결국엔 풀어내지 못했다.

 

처음엔 그냥 배열 원소를 string 으로 변환한 후, string 정렬하면 끝 아니야?? 라고 생각했다.

 

이렇게 풀면 배열로 [3, 30, 34, 5, 9] 가 주어졌을 때 정답은  "9534330" 인데,

 

"9534303" 이 됐다. 흠.. 3 과 30 을 어떻게 바꿔야하나 한참을 고민했는데 도저히 모르겠어서 아예 방법을 바꾸기로 했다.

 

그럼 모든 수의 자릿수를 동일하게 맞추고나서 정렬한 후 원래의 값으로 이어붙이면 되겠구나 (정답 필이 왔다) 라고 생각하여 

 

위 배열의 경우 [3, 30, 34, 5, 9] 을 [(30, 3), (30, 30), (34, 34), (50, 5), (90, 9)] 로 만들고나서 내림차순으로 정렬하니

 

[(90, 9), (50, 5), (34, 34), (30, 3), (30, 30)] 으로 정렬되었고 원래 값을 차례로 붙여서 리턴했다. 9534330 .

 

문제를 클린하게 풀었다는 느낌이 강하게 들었고 정답을 확신했는데 왠걸... 정답률이 40 밖에 안되는것..

 

이때부터 힘이 쭉 빠지며서 맨붕이 왔다.. 대체 뭘 어떻게 해야하나...

 

질문게시판을 보고 각 문자 값을 * 3 해서 정렬하면 된다는 힌트를 봤는데 이 설명을 보고도 이게 뭔 소린가... 하면서 이해를 못했다 ㅡ.ㅡ;;

 

결국엔 다른 분의 풀이를 검색해서 보고나서야 어렴풋.. 하게 이해가 되었다. 

 

내가 이해하기에 이렇다.

 

자릿수를 맞춘다는게 문자열로 비교정렬을 하기 위해서 숫자 자릿수를 맞추는게 아니고 문자 비교를 위해서 동일한 비율로 늘려줘야 

비교가 가능하기 때문에 문자열 * 3을 하고 비교를 하는것이다.

 

내 머리로는 도저히 이런생각을 해낼 자신이 없다.. ㅡ.ㅡ;

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


print(solution([23, 232, 21, 212]))

 

 

관련하여 찾기 힘든 반례를 공유한다

# [30, 3021] => 303021
# [23, 232, 21, 212] => 23 232 212 21
# [383, 38] => "38383"
# [838, 83] => "83883"
# [87, 878] ==> "87887"
# [10, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] ==> "987654321101000"
# [40, 404] ==> "40440"
# [90,908,89,898,10,101,1,8,9] ==> "990908898988110110"