[JAVA] 정렬 Lv.2 / 가장 큰 수

🔗링크

https://programmers.co.kr/learn/courses/30/lessons/42746

코딩테스트 연습 - 가장 큰 수

 

📜문제
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를 문자열로 변환하여 저장한뒤, 정렬하여 차례대로 answer에 붙여주는 방식으로 문제를 해결했다
이중 눈여겨 봐야할것은 Comparator이다

Comparator : 객체 간의 특정한 정렬이 필요할 때, Comparator 인터페이스를 확장해서 특정 기준을 정의하는 compare() 메서드를 구현한다.
(일반적인 정렬이 필요할시 Comparable 사용)

a.compareTo(b)
 -앞에서부터 비교하다 다른 문자열이 나오면 'a-b' 순서로 해당 문자의 아스키코드 값을 뺀 결과(int)를 리턴
 내림차순 : (o2+o1).compareTo(o1+o2);
 오름차순 : (o1+o2).compareTo(o1+o2);

arr을 정렬한뒤 arr의 첫번째 값이 0 인지 아닌지 (주어진 수가 모두 0인 경우) 판별한뒤,
arr안에 있는 문자를 하나씩 꺼내서 answer에 붙여주면 끝.

💻코드

import java.util.*;

class Solution {
    public String solution(int[] numbers) {
        String answer = "";
        
        //1
        String[] arr = new String [numbers.length];
        for(int i=0; i<numbers.length; ++i){
            arr[i]= String.valueOf(numbers[i]);
        }
        
        //2
        Arrays.sort(arr,new Comparator<String>(){
            
            @Override
            public int compare(String s1, String s2){
                return ((s2+s1).compareTo(s1+s2));      //두 String을 합쳐서 큰 쪽이 우선순위 있도록
            }
            
        });
		
        //3
        if(arr[0].equals("0")){		//0으로 이뤄져있을경우 
            return "0";
        }
        
        for(String a: arr){         
            answer += a;
        }     
                
        return answer;
    }
}