[Python : 프로그래머스] 가장 큰 수

문제

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

풀이

가장 단순하게 떠올린 방법은 itertools 라이브러리의 permutations 함수를 이용해서 모든 조합을 구한다음 비교하는 것이었는데, 대부분의 탐색 알고리즘은 O(nlogn)을 넘어가지 않게 구현해야 한다. 이 때문에 이 방식은 완전히 잘못된 접근이다.

“어떻게 하면 한 번의 루프로 모든 비교가 완료될까?”
라는 생각을 떠올리면, 반복문을 수행하기 전에 미리 전처리를 해두면 된다는 결론까지 도달하게 된다.
그리고 이것을 확신으로 만들어주는 힌트가 제한 사항에 나와있다.

• numbers의 길이는 1 이상 100,000 이하입니다.
• numbers의 원소는 0 이상 1,000 이하입니다.
• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

0 <= n <= 1000 같은 작은 범위의 제한사항은 괜히 주는 것이 아니다.
numbers의 모든 원소를 1000과 같은 4자리 수로 만들면 비교가 가능해진다.
단, 이 때 원소를 4자리 수로 만드는 방법에 유의해야하는데, 단순하게 10을 곱해서 만들 경우 12, 121 같은 수에서 문제가 발생하게 된다.

12  -> 1200
121 -> 1210
1200 < 1210
------------
121, 12 -> 12112

내가 구해야하는 값은 12121 이다. 10씩 곱하는 것으로는 계속해서 오답이 발생한다.
다음으로 생각해볼 수 있는 것은 원소의 남는 자리수에 원소를 그대로 덧붙이는 것이다.

12  -> 1212
121 -> 1211
1212 > 1211
------------
12, 121 -> 12121

---

그리고 제출한 첫 코드

def solution(numbers):
    num = list(map(str, numbers))   # int -> str 변환
    num.sort(key=lambda x: x*3, reverse=True) # str * 3 으로 덧붙이기
    
    return "".join(num) # 원소 연결

당연히 정답일거라 생각하고 제출했는데, 틀렸다.
정확한 케이스는 확인하지 못했지만, 아마 결과값의 앞자리가 0으로 시작하는 케이스가 있지 않을까 생각하고 다시 제출했다.

def solution(numbers):
    num = list(map(str, numbers))   # int -> str 변환
    num.sort(key=lambda x: x*3, reverse=True) # str * 3 으로 덧붙이기
    
    return str(int("".join(num))) # 원소 연결

해결!

더 나은 풀이

가장 많은 좋아요를 받은 풀이가 나와 비슷했다. ‘파이썬스럽게’ 해결한 것 같아 뿌듯한 문제였다.
더 정진하자!