[Algorithm] 프로그래머스 정렬 - 가장 큰 수

 

프로그래머스 알고리즘 고득점 kit 정렬 문제를 정리한 내용입니다.

 

문제 : Lv.2 가장 큰 수

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 배열의 값을 String으로 변환하여 새로운 String 배열을 만들어준다.
  String.valueOf(int a) 또는 Integer.toString(int a)를 사용해 int 타입을 String 타입으로 변경시켜준다.

• Arrays.sort() 메서드를 통해서 정렬해준다.
  첫번째 매개변수는 정렬해줄 배열 객체이고 두번째 매개변수는 Comparator(정렬 기준이 저장됨)이다.
  
  
• 문제에서 비교하고자 하는것이 일반적인 수의 오름/내림차순으로의 정렬 값이 아니기 때문에 직접 Comparator를 생성해 이용한다.
  문자열 자체로 결과를 비교하는 방식으로 구현한다. 입력된 두 문자열을 더하는 경우 중 더 큰 값을 기준으로 내림차순 정렬한다.
  (6과 10을 비교하고자 할때 문자열 자체로 더해 610과 106을 비교, 이때 610이 더 큰 값이기 때문에 6이 10보다 큰 수라고 결론 내리고 6, 10 순서로 내림차순 정렬한다.)
  << 아래 코드 처럼 구현할 수 있다. >>

Arrays.sort(strNumbers, new Comparator<String>() {
	@Override
    public int compare(String o1, String o2) {
    	return (o2 + o1).compareTo(o1 + o2);
    }
});

// 오름차순으로 구현
(o1 + o2).compareto(o1 + o2);

// 람다식으로 구현
Arrays.sort(strNumbers, (o1, o2) -> (o2 + o1).compareTo(o1 + o2));

 

• 정렬된 상태로 String 배열 요소들을 하나의 문자열로 만든다.
  
  
• 배열의 값이 {"0", "0", "0,"}인 경우 결과값이 "000"이 아닌 "0"이 될 수 있도록 조건문을 넣어준다.
  이는 결국 크기 순으로 내림차순 하였을 경우 제일 큰 값이 들어있을 첫번째 인덱스의 값이 0일 경우와 같다.

 

 

코드

import java.util.Arrays;
import java.util.Comparator;

public class 가장_큰_수 {

    public static void main(String[] args) {
        System.out.println(solution(new int[]{6, 10, 2}));  //6210
        System.out.println(solution(new int[]{3, 30, 34, 5, 9}));  //9534330
    }

    public static String solution(int[] numbers) {
        String answer = "";
        String[] strNumbers = new String[numbers.length];

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

        Arrays.sort(strNumbers, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return (o2 + o1).compareTo(o1 + o2);
            }
        });

        if (strNumbers[0].equals("0")) {
            return "0";
        }

        answer = String.join("", strNumbers);

        return answer;
    }
}