코딩테스트 고득점 kit, 정렬 - 가장 큰 수

문제 설명

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

 

제한 사항

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

입출력 예

---

이 문제의 key포인트

-> numbers의 원소는 0 이상 1,000 이하입니다.

입출력 예 두번째를 보면 3보다는 34가 먼저 나와야하고 30보다는 3이 먼저 나와야한다.

따라서 34 > 3 > 30 이 관계가 나오도록 만드는게 key포인트이다.

각 numbers를 문자열로 바꾼다음 세번씩 반복해서 비교하면 위와 같은 관계를 만들 수 있다. 

 

이 방법이 생각나지 않아 풀이를 참고했다.

---

자료구조 및 알고리즘: 정렬

---

풀이

완성코드

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

# https://jokerldg.github.io/algorithm/2021/05/06/most-big-number.html

 

처음에는 문자열로 만들어서 정렬해야겠다는 아이디어까지는 가졌지만 그렇게 하면 

["3", "30", "34","5","9"] -> ["9", "5", "34", "30", "3"]이 된다.

• 해결방법
  numbers의 원소는 1000이하 이므로 모든 문자열을 최소 세자리수로 만들 수 있도록 정렬 시 문자열을 3번씩 곱해서 정렬하도록 했다. 이때 lambda함수를 사용하였다.
• 마지막에 출력값을 int로 바꿨다가 str로 표현하는 이유
  numbers가 [0, 0, 0]인 경우 만들 수 있는 가장 큰 수는 "000"이 아닌 0이다.  

---

풀이참고

https://jokerldg.github.io/algorithm/2021/05/06/most-big-number.html

프로그래머스 가장 큰 수 (python 파이썬) - Tech