[프로그래머스] 가장 큰 수 (Java)

 

프로그래머스

완전탐색으로 전체 경우의 수를 비교하기에는 데이터의 양이 너무 많기 때문에(배열 길이: 100,000) 최대값을 구할 수 있는 알고리즘을 찾아 적용해야만 하는 문제였다.

 

- 문자열 배열로 변환

- Comparator 재정의 (기준 : 두 개의 문자열을 앞뒤로 바꿔 붙인 2개의 수를 Integer로 변환했을 때 더 큰 수가 앞으로 오도록) 및 정렬 수행(Arrays.sort())

- StringBuilder를 활용하여 앞에서부터 문자열 전부 이어주기

- 가장 앞자리(가장 큰 수)가 0인 경우 전체가 0이기 때문에 0을 반환 (예: "0000000" -> "0")

- 0이 아닌 경우 정답 반환

 

Note

- Comparator 작성 시 compare 함수의 리턴 타입은 int여야함

import java.util.*;

class Solution {
    public String solution(int[] numbers) {

        String[] arr = new String[numbers.length];
        
        for(int i = 0; i < numbers.length; i++){
            arr[i] = String.valueOf(numbers[i]);
        }
        
        Arrays.sort(arr, new Comparator<String>(){
            public int compare(String s1, String s2){
                return Integer.parseInt(s2 + s1) - Integer.parseInt(s1 + s2);
            }
        });
        
        StringBuilder sb = new StringBuilder();
        
        for(String str : arr){
            sb.append(str);
        }
        
        return sb.charAt(0) == '0' ? "0" : sb.toString();
    }
}