(Lv2) 가장 큰 수

문제 설명

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

제한 사항

• numbers의 길이는 1 이상 100,000 이하입니다.
• numbers의 원소는 0 이상 1,000 이하입니다.
• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

입출력 예

numbersreturn

[6, 10, 2]	"6210"
[3, 30, 34, 5, 9]	"9534330"

---

내 접근 방법

 

1. 먼저 예제에 나와있는 6 10 2에 대해서 어떻게하면 반복문을 돌면서 6102, 6210.. 등등 연결해서 붙일지 고민했다.
2. 두번째로는 주어진 배열이 int형이기 때문에 문자형으로 바꿔야겠다는 생각이 들었다.
3. [6102, 6210, 1062, 1026, 2610, 2106] 이부분을 보고 Arrays.sort 를 사용해서 max값을 뽑아내야겠다고 생각했다.
4. 문자열을 연결할 때 주어진 int형을 String형으로 바꾸고 StringBuilder를 사용해서 append로 연결시켜주면 되겠다고 생각했다.

근데.. 30분정도 고민해봤지만.. 손이 잘 움직이지 않았다.. 결국 다른사람들이 어떻게 풀었나 풀이를 보고 이해하기로 결정!

 

작성한 코드

import java.util.*;
class Solution {
    public String solution(int[] numbers) {
        // numbers : 0또는 양의 정수가 담긴 배열
        String answer = "";
        
        //int 배열을 String 배열로 변환
        String[] arr = new String[numbers.length];
        for (int i = 0; i < numbers.length; i++) {
            arr[i] = (String.valueOf(numbers[i]));
        }
        
        //배열 정렬, 정렬 규칙으로는 2개를 더하여 더 큰 쪽이 우선순위가 있도록 정렬
        Arrays.sort(arr, new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                return (s2+s1).compareTo(s1+s2);
            }
        });
        
        //0000 처럼 0으로만 구성되어있으면 0 return
        if (arr[0].equals("0")) return "0";
        
        //그 외의 경우 순차적으로 연결하여 answer return
        for (int i = 0; i < arr.length; i++) {
            answer+=arr[i];
        }
        return answer;
    }
}

문자열 배열형태로 바꿔주는거까지는 진행하고 Arrays.sort 까지 해줘야 겠구나 까지는 접근했는데.. Comparator까지는 생각을 못했다.

6 10 2가 주어졌을 때 앞의 두개 610 과 102가 연결된걸 비교하는 방법도 놓쳤던 부분이다.

 

알고리즘 공부는 너무 어려운 것 같다.