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

가장 큰 수

---

개인 노션 링크

문제 원본 링크

---

[문제 설명]

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

• numbers : 0 또는 양의 정수가 담긴 배열

순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

[제한사항]

• numbers의 길이는 1 이상 100,000 이하입니다.
• numbers의 원소는 0 이상 1,000 이하입니다.
• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

[입출력 예]

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

---

첫번째 접근 : 숫자끼리 비교

• 배열로 주어진 수들을 temp 리스트로 옮기고 그 중 가장 큰 수를 찾아, list 리스트에 넣는다.
  - 이 과정에서 잦은 추가와 삭제가 예상되어 배열이 아닌 리스트로 접근하였다.

• arrayToList() : 배열을 리스트로 복사하는 메서드

• addMaxNum() : 가장 큰 수를 찾아 list 리스트에 넣는다.
  - 가장 큰 수는 자리수에 상관 없이 첫번째 자리 수가 가장 큰 수를 고른다.

import java.util.ArrayList;
import java.util.List;

class Solution {
    private int maxNumber;
    private final List<Integer> list = new ArrayList<>();
    private final List<Integer> temp = new ArrayList<>();

    public String solution(int[] numbers) {
        arrayToList(temp, numbers);      //배열을 리스트로 복사

        while (!temp.isEmpty()) {        //temp 리스트가 빌 때까지
            maxNumber = temp.get(0);

            for (int i = 1; i < temp.size(); i++) {
                int digit = temp.get(i) / 10;
                addMaxNum(maxNumber, temp.get(i), digit, i);    //최대 수를 판단하여 리스트에 추가
            }
        }

        String answer = list.toString();
        return answer;
    }

    private final void arrayToList(final List list, final int[] array) {
        for (int a : array) {
            list.add(a);
        }
    }

    //각 숫자의 맨 첫 자리수 크기를 비교
    //3과 23을 비교할 경우 3 * 10과 23을 비교
    //단, 이 경우 [34, 3, 5]가 있을 경우 "5343"이 아닌 "5334"로 배치될 수도 있어 문제가 발생
    private final void addMaxNum(final int currentMax, final int num, final int digit, final int index) {
        if (digit < 1) { //1자리수
            if (currentMax < num) {
                maxNumber = num;
                temp.remove(index);
                list.add(maxNumber);
            }
        } else if (digit < 10) { //2자리수
            if (currentMax * 10 < num) {
                maxNumber = num;
                temp.remove(index);
                list.add(maxNumber);
            }
        } else if (digit < 100) { //3자리수
            if (currentMax * 100 < num) {
                maxNumber = num;
                temp.remove(index);
                list.add(maxNumber);
            }
        } else if (digit == 1000) {
            if (currentMax * 1000 < num) {
                maxNumber = num;
                temp.remove(index);
                list.add(maxNumber);
            }
        }
    }
}

//int a가 0~9이면 a / 10 = 0; -> 1미만이면 1자리수
//10~99면 1~9;                -> 10미만이면 2자리수
//100~999면 10~99;            -> 100미만이면 3자리수    

가장 큰 수를 고르는 과정에서 3과 31을 구분하지 못하였고, 이를 보완하려면 마지막 자리 수까지 비교하도록 하는 과정이 필요했다. 다만, 이는 효율성을 만족하지 못한다. (시간 초과)

두번째 접근 : 숫자를 문자열로 변환 후 비교

• 마찬가지로 배열이 아닌 리스트를 이용한다.
• 이후, Comparator 인터페이스의 compare() 메서드를 오버라이딩한다.
  • o1.compare(o2); 는 3과 31이 있을 경우, 단순 숫자만 비교하여 31이 크다고 판단한다.
  • 따라서 (o2+o1).compare(o1+o2); 와 같이 331과 313을 비교하여 3을 크다고 판단한다.
• Arrays.sort()를 통해 정렬된 stringNumbers로부터 향상된 for문을 이용해 하나씩 str에 저장한다.
  • 이 과정에서 가장 큰 수부터 반환이 되는데, 맨 처음이 0이면 뒤에 숫자도 0인 경우이다.
  • 즉, 배열이 {0, 0, 0, ..} 처럼 0으로만 주어진 경우일 땐 "000"이 아니라 "0"을 리턴하도록 한다.

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

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

        String[] stringNumbers = new String[numbers.length];

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

        Arrays.sort(stringNumbers, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                System.out.println((o2+o1) + "과 " + (o1+o2) + " 비교");
                return (o2+o1).compareTo(o1+o2);
            }
        });

        for (String str : stringNumbers) {      //정렬된 순서대로 answer에 추가
            answer += str;
        }

        if (stringNumbers[0].equals("0")) {     //배열이 {0, 0, 0} 처럼 0으로만 주어질 경우 0을 리턴
            return "0";
        }
![](https://velog.velcdn.com/images/dongvelop/post/c7f2be3e-2460-45c1-89d7-b0801a7194eb/image.png)

        return answer;
    }
}

가장 큰 수를 찾는 과정이 간단해져 정렬에 시간을 뺏기지 않았다.

---

전체 코드 보러 가기