Programmers - 가장 큰수 with JAVA (+)

 

문제

문제에는 Integer 리스트가 주어진다.

예를들어, 다음과 같이 주어진다고 가정하자.

[3, 30, 34, 5, 9] 이를 조합해 가장 큰 수를 만드는 문제이다.

 

 

아이디어 & 로직

우선적으로 String으로 바꾼 후 정렬을 해주면 앞자리가 클 수록 앞으로 정렬된다.

또한 앞자리가 같다면 다음 수가 클 수록 앞에 정렬된다.

위의 예시를 String으로 바꾼 후 정렬하면 다음과 같은 결과를 얻을 수 있다.

[9, 5, 34, 30, 3]

하지만 여기서 결과를 만들면 틀렸다. 왜냐하면 303보다 330이 크기 때문이다. 따라서 위와같이 그래도 정렬해서 반환하면 안된다.

조건에서 각 원소는 0부터 1000이하라고 하였다. 따라서 각 요소를 4배로 바꾸면 그 크기 비교가 더 명확해진다.

위의 예시를 4배 반복하면 다음과 같다.

[9999, 5555, 34343434, 30303030, 3333]

이 후, 정렬을하면 3333이 30303030보다 String 상에서 더 크기 때문에 앞에 정렬이 된다.

 

 

1. 데이터를 String으로 변환

2. 4배해서 정렬

3. 모든 결과가 0일 경우 대비해 이런상황에는 0을 반환

4. 3과 다른경우는 합쳐서 반환

 

 

코드

import java.util.*;
class Solution {
    public String solution(int[] numbers) {
        StringBuilder sb = new StringBuilder();
        List<String> check = new ArrayList<>();
        for(int number : numbers){
            check.add(String.valueOf(number));            
        }
        Collections.sort(check, (a, b) -> (b.repeat(4)).compareTo(a.repeat(4)));
        for(String now : check){
            sb.append(now);
        }
        String result = sb.toString();
        if(result.charAt(0) == '0'){
            return "0";
        }
        return result;
    }

}

 

 

왜 앞에 0인 경우 0임을 판단하는 것을 까먹는것인가...

import java.util.*;
class Solution {
    public String solution(int[] numbers) {
        List<List<String>> values = new ArrayList<>();
        for(int i=0; i<numbers.length; i++){
            StringBuilder sb = new StringBuilder();
            List<String> now = new ArrayList<>();
            for(int j=0; j<4; j++){
                sb.append(String.valueOf(numbers[i]));
            }
            now.add(sb.toString());
            now.add(String.valueOf(i));
            values.add(now);
        }
        Collections.sort(values, Comparator.comparing(arr -> arr.get(0)));
        StringBuilder sb = new StringBuilder();
        for(int i=values.size()-1; i>=0; i--){
            int index = Integer.valueOf(values.get(i).get(1));
            sb.append(String.valueOf(numbers[index]));
        }
        if(sb.toString().charAt(0) == '0'){
            return "0";
        }
        return sb.toString();
    }

}