[프로그래머스] 가장 큰 수 / 파이썬 / python / 해시

📌 문제

🤔 문제 설명

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	return
[6, 10, 2]	"6210"
[3, 30, 34, 5, 9]	"9534330"

 

---

🐥 풀이

permutations 써서 풀었다가 다 시간초과  ........  ㅎ
결국 다른 풀이들을 참고하여 해결했다. ㅜ

두가지 풀이가 있다 (자세한 풀이는 주석 참고!)
1. 수들을 새로운 기준으로 정렬 후 조합
   ->  a,b 두 수를 조합해서 만들어진 문자열이 사전순으로 a+b가 더 크다면 a,b 순으로 /  반대라면 b,a 순으로 정렬하는 것.
   cmp_to_key로 comparator 함수를 만들어서 사용!!

2. 모든 숫자들을 문자열 변환 후 3번 곱한 것들을 비교(사전순으로)
    -> 숫자들이 1000이하 이므로 문자열 변환 후 3번 반복해서 더해주면 쉽게 사전순으로 비교가 가능하다!  ㄷㄷ
 

---

👩🏻‍💻 Code

 

1.

 

2.

 

 

3. 내 풀이 (시간초과 ^_^)