0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.
예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.
0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.
package programmers.Sort;
import java.util.ArrayList;
import java.util.Arrays;
public class Q2 {
public static void main(String[] args) {
class Solution {
public String solution(int[] numbers) {
ArrayList<ArrayList<Integer>> digitList = new ArrayList<>();
for (int number : numbers) {
ArrayList<Integer> digit = new ArrayList<>();
if (number == 0) {
digit.add(0);
} else {
int temp = number;
for (int i = 0; i < 3; i++) {
if (temp == 0)
break;
else {
digit.add(0, temp % 10);
temp /= 10;
}
}
}
digitList.add(digit);
}
System.out.println(digitList);
digitList.sort((o1, o2) -> {
if (o1.get(o1.size() - 1) > o2.get(o2.size() - 1)) {
return -1;
} else if (o1.get(o1.size() - 1).equals(o2.get(o2.size() - 1))) {
return 0;
} else {
return 1;
}
});
System.out.println(digitList);
String result = "";
for (ArrayList<Integer> digit : digitList) {
int number = 0;
for (int i = 0; i < digit.size(); i++) {
number += digit.get(i);
number *= 10;
}
number /= 10;
result += "" + number;
}
return result;
}
}
// int[] numbers = {6, 10, 2};
// int[] numbers = {3, 30, 34, 5, 9};
int[] numbers = {3, 30, 134, 5, 9, 0};
Solution solution = new Solution();
System.out.println(solution.solution(numbers));
}
}
→ 제일 앞자리가 큰 수를 기준으로 정렬하여 순서대로 이어 붙히면 가장 큰 수를 만들 수 있다.
→ 정렬을 위해 정수의 자리수를 분리하는 과정을 반복문을 통해 구현하였다.
→ 반복문을 통해 구현하니 실행 시간을 초과하였다.
package programmers.Sort;
import java.util.ArrayList;
public class Q2 {
public static void main(String[] args) {
class Solution {
public String solution(int[] numbers) {
ArrayList<String[]> digitList = new ArrayList<>();
for (int number : numbers) {
String numString = Integer.toString(number);
String[] digit = numString.split("");
digitList.add(digit);
}
digitList.sort((o1, o2) -> {
if (Integer.parseInt(o1[(o1.length - 1)]) > Integer.parseInt(o2[(o2.length - 1)])) {
return -1;
} else if (Integer.parseInt(o1[(o1.length - 1)]) == (Integer.parseInt(o1[(o1.length - 1)]))) {
return 0;
} else {
return 1;
}
});
String result = "";
for (String[] digit : digitList) {
int number = 0;
for (int i = 0; i < digit.length; i++) {
number += Integer.parseInt(digit[i]);
number *= 10;
}
number /= 10;
result += "" + number;
}
return result;
}
}
// int[] numbers = {6, 10, 2};
// int[] numbers = {3, 30, 34, 5, 9};
int[] numbers = {3, 30, 134, 5, 9, 0};
Solution solution = new Solution();
System.out.println(solution.solution(numbers));
}
}
→ 문자열을 통해서 구현을 하더라고 split함수가 내부적으로 반복문을 통해 구현되어 있기 때문에 효율성 문제를 해결하지 못했다.