문제
https://programmers.co.kr/learn/courses/30/lessons/42746
시도한 방법
모든 배열을 돌면서 가장 큰 자리수의 값을 key로 하고, 그 값을 리스트인 value에 add하여 HashMap을 만든다.
value의 리스트들의 값을 모든 경우의 수로 조합하여 가장 큰 값을 만든다.
( 모든 경우의 수 : 시간복잡도 계산해봐야함 )
n (n-1) ... (n - (n-1)) 1 = n^n
n에 numbers의 최대길이인 100000을 입력하니 Infinity가 나옴... ㅋㅋㅋㅋ
key값을 기준으로 내림차순 정렬한다.
만든 큰 값들을 내림차순한 순서대로 읽어서 조합하여 수를 만든다.
compare( o1, o2) 함수에서
o1을 현재값, o2를 비교하는 값으로 간주
양수 반환 : o1값이 크다 == o1을 뒤로 가도록 정렬 = [ o2, o1 ]
다음자리를 계속 비교하는 대신에, 길이가 긴 숫자에 맞춰 짧은 숫자의 자릿수를 맞추고, 그 숫자들을 비교한다.
같은경우,
3 30 330 긴 자리의 숫자와 바로 앞자리 비교
3 36 363
로직이 더러운게.. 뭔가 잘못됐다고 생각함.
해결한 방법
배열 정렬시, 순서 정하는 방법을 아래와 같이 함.
둘이 자리 바꿔서
[6, 10, 2]
6 10 -> 610 > 106
6 2 -> 62 > 26
10 2 -> 102 < 210
6 > 2 > 10
[3, 30, 34, 5, 9]
3 > 30
3 < 34
3 < 5
3 < 9
30 < 34
30 < 5
30 < 9
34 < 5
34 < 9
5 < 9
9 > 5 > 34 > 3 > 30
compare ( a , b ) {
if(ab > ba) return -1;
....
기본적으로 자바는 오름차순이기 때문에 큰 수가 앞에 오도록 하기위해서는 -1을 반환.
내 풀이
import java.lang.Integer;
import java.util.*;
class Solution {
public String solution(int[] numbers_input) {
String answer = "";
Integer[] numbers = Arrays.stream(numbers_input).boxed().toArray( Integer[]::new );
//numbers : [6,2,10]
Arrays.sort(numbers, new Switching());
// "6210"
//answer = String.join(numbers,"");
StringBuffer sb = new StringBuffer();
for(int i=0; i<numbers.length; i++){
//answer += numbers[i];
sb.append(numbers[i]);
}
answer = sb.toString();
// 원소 값이 "모두" 0 일때
// [0, 0, 0, 0, 0] => "0"
//if(Integer.parseInt(answer) == 0) return "0";
if(answer.toCharArray()[0] == '0' ) return "0";
return answer;
}}
class Switching implements Comparator{
@Override
public int compare(Integer a, Integer b){
int ab = Integer.parseInt(a+""+b);
int ba = Integer.parseInt(b+""+a);
if(ab > ba) return -1; // 큰수가 앞으로 가야하므로 descending 형태
if(ba > ab) return 1;
return 0;
}}
후기
- Comparator는 int 과 같은 기본형 대신 Integer을 사용해야 했다. 이때 나는 Arrays.sort를 사용하기 위해 int[] => Integer[] 관련 코드를 썼는데 이는 상당히 복잡하다.
하지만, Collections.sort를 쓴다면 List \ <Integer >에 int[]의 값들을 담아 Collections.sort ( List, Comparator... ) 로 간단히 사용할 수 있다. - 처음에 0000 인 경우를 고려하지 못했다.
- 0000 인 경우를 잡아내기 위해 Integer.parseInt를 썼는데 0000 인 경우만 빼고는 런타임에러가 났다.
느낀점
예전에 못풀었던 문제인데 정렬을 사용한 아이디어 덕에 풀 수 있었다. 여러 수가 아닌, 정렬 로직에서 ( compare(a, b) ... ) 사용될 단 2개의 수만 고려하면 되는 것이었다.
