[프로그래머스] 가장 큰 수 -JAVA

 

 

가장 큰 수

문제 설명

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

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

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

제한 사항

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

입출력 예

 

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

 

 

풀이

정렬을 이용해서 풀면 된다.

맨 처음 잘못 푼 풀이에서는

문자열의 각 요소별로 짤라서 리스트에 넣어서

리스트를 돌면서 각 자리에 해당하는 int에 따라 구현했었다

 

class Node implements Comparable<Node>{
    int num;
    Node(int num){
        this.num = num;
    }
    public int compareTo(Node o) {
    
        ArrayList<Integer>this_num = new ArrayList<>();
        ArrayList<Integer>o_num = new ArrayList<>();
        int a = this.num;
        int b = o.num;
        while(a>=10) {
            this_num.add(a%10);
            a/=10;
        }
        this_num.add(a);
        while(b>=10) {
            o_num.add(b%10);
            b/=10;
        }
        o_num.add(b);
        int this_size = this_num.size();
        int o_size = o_num.size();
        int tmp_a =0;
        int tmp_b = 0;
        while(this_size!=0 && o_size !=0) {
​
            tmp_a = this_num.get(this_size-1);
            tmp_b = o_num.get(o_size-1);
            
            System.out.println(tmp_a+" "+tmp_b);
            if(tmp_a > tmp_b) { // this.num 을 리턴해야됨
                return -1;
            }
            else if(tmp_b > tmp_a) {
                return 1;
            }
            this_size --;
            o_size--;
        }
        if(this_size==0 && o_size ==0) {
            return 1;
        }
        else if(o_size ==0) {
            if(tmp_b> this_num.get(this_size-1)) {
                return 1;
            }
            else {
                return -1;
            }
        }
        else {
            if(tmp_a> o_num.get(o_size-1)) {
                return -1;
            }
            else {
                return 1;
            }
        }
    }
}

 

근데 이렇게 할 필요가 없었다.

비교 해야하는 a,b를 string 형으로 받고

a+b를 한 값과 b+a 한 값을 비교해서 return 하면 되는 것이였다.

예를들어서 String a = "6000" Stringg b = "9"

라고 했을때

a+b = 60009

b+a = 96000

 

나처럼 각각 자리별로 숫자를 끌고와서 리스트에 넣고 또 그에 해당하는 인덱스를 비교 할 게 아니라

저렇게 해야 한다.

 

그리고 주어지는 numbers배열이 [0,0,0,0] 일 경우 그냥 출력하면

0000으로 출력되지만 실제로는 값이 0이 나와야한다.

 

이는 정렬을 마친 후 배열의 첫번째인덱스가 0 이면 return "0"을 통해 해결 할 수 있었다.

 

전체코드

 

x
import java.util.*;
class Solution {
    public static String solution(int[] numbers) {
       String answer = "";
       String arr [] = new String[numbers.length];
       for(int i=0; i<arr.length; i++) {
           arr[i] = Integer.toString(numbers[i]);
       }
       Arrays.sort(arr, new Comparator<String>() {
           @Override
           public int compare(String s1, String s2) {
               int a = Integer.parseInt(s1+s2);
               int b = Integer.parseInt(s2+s1);
               return b-a;
           }
       });
       
       if(arr[0].equals("0")) {
           return "0";
       }
       for(int i=0; i<arr.length; i++) {
           answer+=arr[i];
       }
       return answer;
   }
}