[java] 프로그래머스 - 가장 큰 수

문제

프로그래머스-가장 큰 수

주어진 정수를 이용해 만들 수 있는 수 중에서 가장 큰 수를 찾는 문제.

• 예시
  [6, 10, 2] 가 주어졌을 때 3개의 수로 만들 수 있는 수는 [6102, 6210, 1062, 1026, 2610, 2106] 가 있다
  이 중에서 가장 큰 수는 6210이다

풀이

• 제한 사항
  numbers : 주어지는 정수 배열 이때 numbers의 길이는 1이상 100,000 이하이다 numbers의 원소는 0이상 1,000 이하이다
  정답은 문자열로 바꾸어 리턴한다

입력받는 numbers의 길이때문에 순열로 답을 구하려면 당연히 시간이 터진다
배열을 정렬 한 다음 큰 순서대로 이어붙여 문자열(답)을 만들어야하는데
정렬의 우선순위? 기준?을 어떻게 구현해야할 지 생각을 해봐야했다

우선 입력받은 정수를 String으로 변환해 List에 넣고 sort한다
헷갈림을 방지하기 위해 작은 수를 앞으로 먼저오게 했다

정렬 시 비교할 문자열 2개를 o1,o2라고 할 때
o1이 먼저오는 문자열과 o2가 먼저오는 문자열을 만들어 두 문자열을 비교했다

o1= “4”, o2= “30” 이라고 한다면
o1이 먼저오는 문자열은 “430”, o2이 먼저오는 문자열은 “304”가 된다
두 문자열을 compareTo를 사용해 작은 값이 앞으로 가게 배열을 정렬한다

compareTo(String A, String B)

A와 B가 같으면 0을 리턴
A가 B보다 작으면(사전에서 앞에있으면) 음수를 반환
A가 B보다 (사전에서 뒤에있으면) 양수를 반환

우선순위 시행착오

1. 두 문자열의 길이가 같으면 그대로 compareTo하고, 다른 경우 앞자리부터 비교하며 비교값을 리턴함
   -> [3, 30, 34, 5, 9]같은 경우에서 30 < 3 < 34 의 우선순위를 가져야한다.
   이 부분에 기준을 맞춰 3과 34의 비교일 때 3에게 자리수를 맞추기위해 30으로 변경 후 34와 비교하면 3 < 34 가 됨
   30과 3의 경우 3을 자리수를 맞춰 30으로 만들면 같으므로 자리수가 짧은게 큰 우선순위를 가짐
   하지만 해당 우선순위로 30, 3, 31를 비교하면 30 < 3 < 31이 나오지만 (31330)
   30 < 31 < 3 으로 33130이 더 큰 경우가 발생한다
2. @Override compare에서 리턴값을 임의로 지정할 때
   두 문자열에서 앞자리부터 반복하며 위의 방법과 비슷하게 길이가 다르면
   앞에 문자열이 작은경우 -1, 앞의 문자열이 큰 경우 1을 리턴하게 했다
   compareTo에서 숫자를 리턴할 때 문자열의 차이를 숫자로 리턴하므로 임의지정하면 두 문자열의 우선순위는 가를 수 있겠지만
   전체적인 배열의 순서는 달라진다
3. 주어지는 정수배열의 원소는 0이상이므로 0이 들어가는 경우
   만일 [0, 0, 0, 0]이 주어지고 정렬 후 0000이 완성되었을 때
   0000이 아닌 0이 리턴되어야한다
   즉, 0에대한 판별이 들어가야한다

소스코드

import java.util.ArrayList;
import java.util.Comparator;
class Solution {
public String solution(int[] numbers) {
		ArrayList<String> arr = new ArrayList<>();
		for (int i = 0; i < numbers.length; i++) {
			arr.add(numbers[i] + "");
		}
		arr.sort(new Comparator<String>() {

			@Override
			public int compare(String o1, String o2) { // 4, 30
				String o1First = o1 + o2; // 430
				String o2First = o2 + o1; // 304
				return o1First.compareTo(o2First);
			}
		});
		// 뒤에서부터 답 문자열에 포함하기
		StringBuilder sb = new StringBuilder();
		for (int i = arr.size() - 1; i > -1; i--) {
			sb.append(arr.get(i));
		}
		
		if(Double.parseDouble(sb.toString())==0)
			return "0";
		return sb.toString();
	}
}

다른사람의 코드(0을 판단하는 부분)

...
if(answer.charAt(0) == '0') {
            return "0";
}
...