[프로그래머스/파이썬/자바] 가장 큰 수

 

출처

---

문제 설명

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"

---

풀이

우선 numbers를 모두 합치면 int의 범위를 초과할 수 있으므로 string배열로 변화시킨다.

원소의 개수가 1000이하이므로 조합으로 해결하면 시간초과가 발생한다.

정렬을 하는 아이디어는 두가지의 원소를 합쳐서 비교했을때, 더 큰 수를 앞에 정렬하고 마지막에 정렬된 배열의 값을 순서대로 붙이면 된다.

 

예를 들면, 3과 32라는 숫자가 있다고 치자.

이를 붙이면 332 또는 323이라는 숫자가 되기때문에 3이 앞서 존재해야 한다.

이를 다르게 해석하면 두수를 붙일 때, 앞 글자부터 비교하는데 더 길이가 작은 수의 앞부분이 반복되면서 이를 비교하는 것을 알 수 있다.

 

따라서 정렬을 할때, 두 수를 합쳐보고 큰수가 되게 정렬할 수도 있고,

작은 수를 반복시켜 앞에서 부터 비교해봐도 된다.

코드