[프로그래머스-level 2(정렬) 자바/java] 가장 큰 수 _디버깅의 눈물

https://school.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 합니다.

입출력 예numbersreturn

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

---

※ 공지 - 2021년 10월 20일 테스트케이스가 추가되었습니다.

 

---

 

 

체크 포인트

 

1. 정렬 문제

 

-정수 배열 numbers의 각 원소를 '내림차순' 정렬해 만들 수 있는 가장 큰 수를 출력하는 문제

-정렬의 방법을 어떻게 할 것인가가 핵심이다. 

 

2.Arrays.sort()를 활용한 숫자 형태의 문자열 정렬

 

-직접 정렬을 시도하려고 했지만, numbers 배열의 길이가 최대 100,000인 것을 보고 메모리 초과를 야기할 것으로 생각해 다른 방법을 구상했다.

-구글링 결과 Arrays.sort() 메서드에 숫자형태로 된 문자열의 정렬 기능이 있음을 알고 활용했다.

 

 

 

테스트 케이스 1번[6, 10 ,2]의 예로 들 때,

 

        // Comparator를 활용한 문자열 내림차순 정렬
        Arrays.sort(arr, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return (o2+o1).compareTo(o1+o2);
            }
        });

 

 

// 비교되는 순서
o1 : 10 , o2 : 6
o1 : 2 , o2 : 10
o1 : 2 , o2 : 10
o1 : 2 , o2 : 6

 

 

위와 같은 순서로 o1과 o2가 비교/정렬 되는 것을 확인할 수 있다.

 

구체적으로 보면, o2(6)+o1(10) = 610과 o1(10)+o2(6) = 106 중에서 610이 더 큰 문자열 수가 되기 때문에 6은 10보다 앞자리에 위치하게 되는 것이다.

 

같은 원리로, o2(10)+o1(2) = 102와 o1(2)+o2(10) = 210 중에서 210이 더 큰 문자열 수가 되기 때문에 2는 10보다 앞자리에 위치하게 되는 것이다.

 

위와 같은 정렬이 반복되며 문자열 내림차순 정렬이 진행된다.

 

 

풀이

 

import java.util.*;

class Solution {
    public String solution(int[] numbers) {
        
        String answer = "";

        // 정렬 문제

        // 주어진 숫자를 문자열 배열로 받아준다.
        String[] arr = new String[numbers.length];

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

        // Comparator를 활용한 문자열 내림차순 정렬
        Arrays.sort(arr, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return (o2+o1).compareTo(o1+o2);
            }
        });

        // 맨 앞자리 숫자가 0인 경우,
        if(arr[0].equals("0")){
            answer = "0";
        }
        // 맨 앞자리 숫자가 0이 아닌 경우,
        else{
            for (int i=0; i<arr.length; i++){
                answer += arr[i];
            }
        }

        return answer;
    }
}