[Algorithm] [Python] Programmers - 가장 큰 수

Programmers - 가장 큰 수

문제 설명

---

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 : [6, 10, 2] , output : "6210"

 

numbers : [3, 30, 34, 5, 9] , output : "9534330

 

제출 코드

---

1차 제출 코드

def solution(numbers):
    from itertools import permutations
    numbers = list(map(str,numbers))                        
    tmp = list(map(''.join, permutations(numbers)))
    return max(tmp)

 

1차 제출한 코드는 permutation 모듈을 활용하였다.

 

문제에 주어진 테스트케이스는 만족하지만 역시 시간 초과가 떳다.

 

lambda를 이용해서 정렬을 시도했으나 적절한 정렬 조건을 찾지 못했다..

 

계속 고민해보다가 도저히 생각이 안나서 다른 사람들의 풀이를 살펴봤다.

 

Python

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

 

Swift

func solution(_ numbers: [Int]) -> String {
    let answer = numbers.map({ String ($0)}).sorted(by: {$0 + $1 > $1 + $0})

    return answer[0] == "0" ? "0" : answer.joined()
}

 

코드 해설

---

처음에 파이썬 코드를 보고 왜 저렇게 정렬을 진행하는지 이해를 하지 못했다.

 

위 코드에서의 정렬의 핵심은 문자열 정렬 이다.

 

numbers = list(map(str, numbers))

모든 numbers 내 int형 원소들을 str형으로 변환하여 리스트에 저장한다.

 

numbers.sort(key=lambda x:x*3, reverse = True)

각 원소를 3번씩 연속한 값들을 기준으로 내림차순 정렬한다.

 

세번 문자열을 추가하는 이유는 원소들이 0이상 1000이하 라는 범위를 갖기 때문이다.

 

여기서, 문자열의 정렬이 진행된다.

 

'3' 과 '30'을 3번씩 곱한 값 두개를 예시로 살펴보도록 한다.

 

'333' 과 '303030'이 존재한다. 당연 이 두 문자열을 정수로 보면 303030이 크다는 것을 알 수 있다.

 

하지만, 문자열의 대소비교는 ascii로 변환되서 맨 앞의 숫자부터 비교하도록 한다.

 

 

0번쨰 인덱스 값은 모두 3으로 동일하다, 1번째 인덱스 값은 3과 0으로 나뉘어지며 두 문자의 대소비교시 3이 더 크다는 것을 알 수 있다.

 

 

따라서, '333'과 '303030'두 문자열을 비교하면 '333'이 더 크다는 결론을 확인할 수 있다.

 

이 정렬 방법을 테스트케이스 [6, 10, 2]에 적용해본다.

 

['666', '101010', '222'] 를 내림차순 정렬하면 ['666', '222', '101010']이 되어 ['6','2','10']으로 정렬이된다.

 

전혀 생각하지 못했던 정렬 방법이다.