1. 문제 설명
0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.
예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.
0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.
2. 제한사항
- numbers의 길이는 1 이상 100,000 이하입니다.
- numbers의 원소는 0 이상 1,000 이하입니다.
- 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.
3. 입출력예
| numbers | return |
| [6, 10, 2] | "6210" |
| [3, 30, 34, 5, 9] | "9534330" |
4. 풀이 과정
Solution 1( 실패 )
- 숫자 배열을 문자 배열로 변환
- 문자열 비교하여 큰 수 부터 정렬
- 하나의 문자열로 합쳐서 반환
단순하게 " 문자로 만들어서 큰 것 부터 나열하면 되지 않을까? " 라고 생각했는데 엉뚱한 결과가 나왔다.
public String solution(int[] numbers) {
String[] inputV = new String[numbers.length];
for(int i=0; i<numbers.length; i++){
inputV[i] = String.valueOf(numbers[i]);
}
return compare(inputV);
}
public String compare(String[] inputV){
for(int i = 0; i<inputV.length-1; i++) {
for(int j = i+1; j<inputV.length; j++){
String now = inputV[i];
String next = inputV[j];
int compareV = now.compareTo(next);
if(compareV > 0) {
inputV[i] = now;
inputV[j] = next;
} else{
inputV[i] = next;
inputV[j] = now;
}
}
}
return String.join("",inputV);
}
두번째 입력 값에 대하여 9 > 5 > 34 > 30 > 3 으로 계산이 되었다. ( 문자만 비교했을 땐 그게 맞긴 하네.)
Solution2( 실패 )
- 숫자 배열을 문자 배열로 변환
- 두 문자열 더한 것을 비교하여 큰 수 부터 정렬( ex, [30, 3] => (330 > 303) => [3, 30] )
- 하나의 문자열로 합쳐서 반환
compareV 를 변경해 주었더니 예제는 통과했다. (테스트는 통과하지 못했다. )
// int compareV = now.compareTo(next);
int compareV = (now+next).compareTo(next+now);
Solution3 ( 성공 )
1. 시간초과 : 조건문을 개선한다. ( bubble sort -> java library 사용 )
2. 테스트 11 실패 : [0, 0, 0] 배열이 들어와서 답이 "000" 인 경우 => "0"으로 반환
public String solution(int[] numbers) {
String[] inputV = new String[numbers.length];
for(int i=0; i<numbers.length; i++){
inputV[i] = String.valueOf(numbers[i]);
}
// 라이브러리를 사용하여 비교 및 정렬 끝!
Arrays.sort(inputV, new Comparator<String>(){
public int compare(String s1, String s2){
return (s2+s1).compareTo(s1+s2);
}
});
String answer = "";
for(String s : inputV) answer += s;
// 0 일 경우
if(inputV[0].equals("0")) return "0";
return String.join("",inputV);
}
Solution4 (Solution3 리팩토링)
- 자바 8 람다 함수 사용
Comparator 객체는 메서드가 하나 뿐인 함수형 인터페이스를 구현하기 때문에 람다 함수로 대체가 가능.
// 라이브러리를 사용하여 비교 및 정렬 끝!
Arrays.sort(inputV, new Comparator<String>(){
public int compare(String s1, String s2){
return (s2+s1).compareTo(s1+s2);
}
});=>
Arrays.sort(inputV, (s1, s2) -> {
return (s2+s1).compareTo(s1+s2);
});
- static method를 사용하여 문자열 배열을 문자열로 변환 ( java8 릴리스에 추가 )
String answer = "";
for(String s : inputV) answer += s;=>
String answer = String.join("",inputV);
- 권장되는 문자열 비교 방법
if(inputV[0].equals("0")) return "0";=>
if(answer.startsWith("0")) return "0";
- 최종 코드
public String solution(int[] numbers) {
String[] inputV = new String[numbers.length];
// 숫자 배열을 문자 배열로 변환
for(int i=0; i<numbers.length; i++){
inputV[i] = String.valueOf(numbers[i]);
}
// 내림차순으로 정렬
Arrays.sort(inputV, (s1, s2) -> {
return (s2+s1).compareTo(s1+s2);
});
// 문자열 조합 및 예외 처리
String answer = String.join("",inputV);
if(answer.startsWith("0")) return "0";
return answer;
}
Solution5 ( Solution4 리팩토링 )
- JAVA Stream 사용
import java.util.stream.*;
public String solution(int[] numbers) {
String answer = IntStream.of(numbers)
// .mapToObj(n -> String.valueOf(n)) // static method 사용 권장
.mapToObj(String::valueOf) //method reference 로 축약 가능
.sorted((s1, s2) -> (s2+s1).compareTo(s1+s2))
.collect(Collectors.joining());
if(answer.startsWith("0")) return "0";
return answer;
}
5. 결과
Solution2
Solution 3
Solution 4
Solution 5
6. 마치며
뭔가 결과를 보면서 어떤게 시간이 제일 적게 걸리는지 보는것도 재밌어서 채점 결과까지 올리게된다. ㅎㅅㅎ
java 8 부터 뭔가 많이 생긴것같다. Stream은 정말 유용하면서도 너무 생소하다.
빨리 친해지도록 노력해야지.!
댓글