since 2019.

1 minute read

Updated:

문제 설명

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”

해결 방법

  1. 숫자 배열을 문자 배열로 바꾼다.
  2. 문자 배열을 비교하여 내림차순으로 정렬한다.
  3. 문자열을 조합한다.

구현 코드

  1. 버블 정렬
    • 버블 정렬을 사용하면 시간 초과로 테스트 통과가 안되는 문제 발생
class Solution {
    public String solution(int[] numbers) {

        String[] strAry = new String[numbers.length];
        for (int i = 0; i < numbers.length; i++){
            strAry[i] = String.valueOf(numbers[i]);
        }

        // 버블정렬 사용하여 내림차순으로 정렬
        for(int i = 0; i < strAry.length - 1; i++){
            for(int j = 0; j <strAry.length - (i + 1); j++) {
                String a = strAry[j] + strAry[j+1];
                String b = strAry[j+1] + strAry[j];
                if(a.compareTo(b) < 0){
                    String temp = strAry[j];
                    strAry[j] = strAry[j+1];
                    strAry[j+1] = temp;
                }
            }
        }

        String answer = String.join("", strAry);
        
        if(strAry[0].equals("0")){
            return "0";
        }
        return answer;
    }
}
  1. Arrays.sort() 라이브러리 사용하여 구현
import java.util.*;

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

        // 숫자 배열을 문자열로 변환
        String[] strAry = new String[numbers.length];
        for (int i = 0; i < numbers.length; i++){
            strAry[i] = String.valueOf(numbers[i]);
        }

        // 문자열을 비교하여 정렬
        Arrays.sort(strAry, new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                return (s2+s1).compareTo(s1+s2);
            }
        });

        // 문자열 배열을 이어붙인다.
        String answer = String.join("", strAry);

        if(strAry[0].equals("0")){
            return "0";
        }
        return answer;
    }
}
  1. stream 라이브러리 사용하여 코드 리팩토링
import java.util.stream.*;

class Solution {
    public String solution(int[] numbers) {
        
        String answer = IntStream.of(numbers)
            .mapToObj(String::valueOf) 
            .sorted((s1,s2) -> (s2+s1).compareTo(s1+s2))   
            .collect(Collectors.joining()); 

        if(answer.startsWith("0")){
            return "0";
        }
        return answer;
    }
}

TIP.

  • Java 언어를 사용한다 == Java가 제공하는 라이브러리를 사용한다.
  • 기본 라이브러리인 java.lang.과 java.util.의 사용법을 숙지한다.

You may also enjoy