[JAVA][Level2]PROGRAMMERS 가장 큰 수

정렬을 이용해서 문제를 해결하는 문제

---

가장 큰 수

---

문제 설명

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"

주어진 문제

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

---

나의 문제풀이

import java.util.*;

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

        // 모든 수를 4자리로 만들어 비교를 하기 위해 리스트 만들기
        List<Integer> list = new ArrayList<>();
        for (int number : numbers) {
            if (number < 10) {
                list.add(number * 1111);
            } else if (number < 100) {
                list.add(number * 101);
            } else if (number < 1000) {
                list.add(number * 1001 / 100);
            } else {
                list.add(number);
            }
        }
        // 복사본 배열 만들기
        int[] tmepNumbers = list.stream().mapToInt(x -> x).toArray();

        // 4자리로 만든 숫자들로 비교를 하여 선택정렬을 이용해서 내림차순 정렬
        int temp = 0;
        for (int i = 0; i < numbers.length - 1; i++) {
            int maxIndex = i;

            for (int j = i + 1; j < numbers.length; j++) {
                if (tmepNumbers[maxIndex] < tmepNumbers[j]) {
                    maxIndex = j;
                }
            }

            temp = numbers[maxIndex];
            numbers[maxIndex] = numbers[i];
            numbers[i] = temp;

            temp = tmepNumbers[maxIndex];
            tmepNumbers[maxIndex] = tmepNumbers[i];
            tmepNumbers[i] = temp;
        }

        // 정렬된 배열을 문자열에 추가
        for (int job : numbers) {
            // 맨 앞자리가 0일 경우 해당 숫자로 교체 처리
            if (builder.toString().equals("0")) {
                builder = new StringBuilder(String.valueOf(job));
            } else {
                builder.append(job);
            }
            // if (answer.equals("0")) {
            //     answer = String.valueOf(job);
            // } else {
            //     answer += job;
            // }
        }
         
        return answer = builder.toString();
    }
}

• 배열 내 수를 비교하기 위해서 모든 수를 4자리로 만들어 리스트에 넣어준다.
• 리스트를 이용해 변경된 값으로 된 배열을 만든다.
• 이중 for문을 이용해 가장 큰 값을 앞으로 가져와 내림차순 정렬을 한다.
• 정렬된 배열을 문자열에 추가한다.
  • 앞서 추가된 문자열이 0일 경우 StringBuilder를 문자열로 생성한다.
  • 앞서 추가된 문자열이 0이 아닐 경우 StringBuilder에 문자열에 추가한다.

추가 입출력 예

numbers	return
[0, 0, 0, 0, 0]	"0"
[4, 453, 7, 39, 16]	"745343916"
[1000, 1]	"11000"

자릿수가 다른 숫자들의 크기를 비교하기 위해서는 앞자리를 비교해야 하는데, 자릿수별로 잘라서 비교하기보다는 모든 수를 똑같은 자릿수로 만들어 비교를 하는 게 빠르기 때문에 모든 수를 동일한 자릿수로 변경한 배열을 만들어준다. 그 후, 복사한 배열을 이용해서 내림차순으로 정렬해 줄 때, 기존의 배열의 순서도 같이 정렬해 주면 가장 큰 수로 정렬이 된다. 마지막으로 정렬한 배열을 문자열로 변경해 출력하면 된다.
복사본 배열을 만들 때 리스트를 만들어 배열을 만들거나 직접 배열을 만들어서 입력을 해도 되는데 따로 처리 속도 차이는 별로 나지 않고 정렬된 배열을 문자열로 추가하는 부분에 있어서 String으로 바로 추가하는 것보다 StringBuilder를 이용하는 게 조금 더 빨랐다.

 

 

문제 출처 - https://school.programmers.co.kr/learn/courses/30/lessons/42746#