[LeetCode] 179. Largest Number

Problem

Given a list of non-negative integers nums, arrange them such that they form the largest number and return it.

Since the result may be very large, so you need to return a string instead of an integer.

Example 1:

Input: nums = [10,2]
Output: "210"

Example 2:

Input: nums = [3,30,34,5,9]
Output: "9534330"

Constraints:

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 10^9

---

Solution

class Solution {
    public String largestNumber(int[] nums) {
        String[] strNums = new String[nums.length];
        for (int i = 0; i < nums.length; i++)
            strNums[i] = String.valueOf(nums[i]);
        Comparator<String> comp = new Comparator<String>() {
		        @Override
		        public int compare(String str1, String str2) {
		            String s1 = str1 + str2;
				        String s2 = str2 + str1;
				        return s2.compareTo(s1);
		        }
	      };
        // Arrays.sort(strNums, (a, b) -> (b + a).compareTo(a + b));
        Arrays.sort(strNums, comp);
        if (strNums[0].charAt(0) == '0') return "0";
        StringBuilder sb = new StringBuilder();
        for (String str : strNums)
            sb.append(str);
        return sb.toString();
    }
}

Explanation

• 아래와 같이 예시 2의 경우를 살펴보면 배열 nums의 요소들이 반환할 문자열에서 자리하는 순서가 있다.

|Example2|||||| |:—:|:—:|:—:|:—:|:—:|:—:| |정렬 전 요소|3|30|34|5|9| |정렬 순서|4|5|3|2|1| |정렬 후 요소|9|5|34|3|30|

• 위와 같이 배열 nums를 정렬해준 뒤 문자열로 만들어서 반환하면 문제를 해결할 수 있다. 하지만 배열 nums는 정수로 이루어져 있기 때문에 문제에서 원하는 정렬 기준을 충족 시킬 수 없다.
• 일반적인 정수의 정렬은 배열 속 두 요소의 대소관계를 전부 비교하여 정렬을 진행한다. 따라서 본 문제에서 원하는 정렬 기준 또한 두 요소를 비교하여 충족시킬 수 있다.
• 두 요소를 비교하여 정렬하려면 두 요소를 이어붙였을 때의 대소크기를 비교하면 된다. 하지만 정수 배열보다는 문자열 배열에서 두 요소를 이어붙이기가 편하고, 반환타입 역시 문자열이기 때문에 문자열 배열을 선언하고 배열 nums의 값을 옮겨준다.

  String[] strNums = new String[nums.length];
  for (int i = 0; i < nums.length; i++)
    strNums[i] = String.valueOf(nums[i]);
  

• 배열 strNums를 정렬하기 위해선 Arrays.sort()메서드를 사용해야 하지만 일반적인 정수 배열의 정렬이 아니기 때문에, 파라미터로 배열 속 요소들을 비교할 수 있는 객체를 전달해야 한다.
• 두 문자열을 이어 대소비교를 진행하는, 배열 strNums의 정렬의 기준이 되는 객체를 선언한다.

  Comparator<String> comp = new Comparator<String>() {
    @Override
    public int compare(String str1, String str2) {
        String s1 = str1 + str2;
        String s2 = str2 + str1;
        return s2.compareTo(s1);
    }
  };
  

• 배열 strNums를 정렬 기준을 통해 정렬해준다.

  Arrays.sort(strNums, comp);
  

• 배열 strNums의 요소에 “0”은 정렬 후 항상 마지막에 자리해야 한다. 하지만 정렬 후 에도 “0”이 마지막에 있다는 것은 배열 strNums의 요소가 “0”만을 포함하고 있다는 의미가 되고 “0”을 반환해야 한다. 이를 반영하여 if조건문을 작성한다.

  if (strNums[0].charAt(0) == '0') return "0";
  

• 정렬된 배열 strNums의 요소들을 이어 붙이기 위해 StringBuilder을 선언하고 이어붙인다.
• 완성된 StringBuilder을 문자열로 변환 후 반환한다.

  StringBuilder sb = new StringBuilder();
  for (String str : strNums)
    sb.append(str);
  return sb.toString();