[정렬] 가장 큰 수

문제 설명

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"

 

 

---

알고리즘 정리

우선 숫자의 앞에 자리가 가장 큰 수를 찾는다.

숫자가 같은 경우 조합의 숫자가 더 큰 수 (AB, BA 중 더 큰 수) 순으로 정리한다.

 

풀이방법

compareTo 의 문자열 비교는 이런 특징을 가지고 있다.

1. 맨 앞의 문자부터 한 문자씩 아스키 코드 값으로 뺀 수를 리턴한다.
2. 문자가 같으면 다음 문자를 비교 한다.
3. 문자수가 다르면 남은 자리수를 리턴한다. (ACBD, ACB 이면 1을 리턴) 

그래서 compareTo 의 문자열을 비교방법과

이렇게 비교한 것을 Arrays 의 sort 를 이용하면 쉽게 해결할 수 있다.

compareTo의 더 다양한 예제를 보고 싶다면 여기로...

---

코드

	import java.util.Arrays;
	class Solution {
	public String solution(int[] numbers) {
	String answer = "";
	String [] arr = new String[numbers.length];
	for(int i = 0 ; i < numbers.length ; i++)
	arr[i] = String.valueOf(numbers[i]);
	//두 문자열의 합을 앞의 한글자씩 아스키 값으로 비교하여 더 큰 순으로 정렬
	Arrays.sort(arr, (o1, o2) -> (o2 + o1).compareTo(o1 + o2));
	//0 이상이기 때문에 0으로만 된 case 가 존재할수 있다.
	//그러면 0+0+... 이 0이 아닌 00, 000 ... 으로 값이 달라질 수 있기에 아래코드 추가
	if (arr[0].equals("0")) {
	return "0";
	}
	for(String ar:arr)
	answer += ar;
	return answer;
	}
	}

view raw LargestNumber.java hosted with ❤ by GitHub

결과 : 테스트 예제 통과 / 테스트 실패

초반에는 고려하지 못한 경우의 수가 있었는데

0 이상의 값이 들어올 수 있으므로 전부 0 일 경우를 위한 예외처리가 안되어 있어서 추가한 결과

 

결과 : 테스트 예제 통과 / 테스트 통과

다른 algorithm 소스도 보기

 

위 코드로 테스트를 통과하긴 했지만
좀 더 성능을 위해 리팩토링이 필요하긴 하다.
문자 조합을 한다면 스트링이 아니라 StringBuilder 를 쓰는게 낫다고 한다.
왜 일까? Java 에 String 에 대해 더 알고 싶으면 여기로...