[프로그래머스 42746번] 가장 큰 수

문제

번호

[프로그래머스 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 합니다.

입출력 예

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

언어

JAVA

---

풀이

문제 원리는 간단하지만 푸는 것은 꽤 헤매었다.

 

우선 가장 큰 수를 만들어야 된다는 것은

1. input으로 들어온 <pre>numbers</pre>을 적당한 기준으로 정렬을 하고,
2. 정렬된 <pre>numbers</pre>을 쭉 이어 붙인 후 반환하면 된다.

 

처음 시도한 코드들

처음에는 문제를 너무 단순하게 생각하였다. "가장 큰 글자 → 작은 글자 순으로 배치하면 가장 커지겠지? 대신200과 2에서는 2가 200보다 우선되는 것이 크니까, 뒤에 0이 붙는 건 다 빼고 비교도 해야겠다!" 라고 생각한 것이다.

그래서 아래 코드와 같이 뒤에 붙은 0을 모두 없애고 두개가 같다면 원래의 길이가 더 짧은 것을 우선되도록 코드를 작성하였다.

Arrays.sort(numToStr, new Comparator<String>() {
    @Override
    public int compare(String o1, String o2) {
        String o1_trim = o1.replaceAll("0+$", "");
        String o2_trim = o2.replaceAll("0+$", "");

        if(o1_trim.equals(o2_trim)) {
            return Integer.compare(o1.length(), o2.length());
        }
        else return  o2.compareTo(o1);
    }
});

 

그러나 반례가 생겼다. [40, 403]이 바로 그것이다.

이 예제에서 만들 수 있는 가장 큰 수는 40403이지만 위 코드대로라면 40340이 되어버린다.

 

그래서 생각을 바꿨다. "만약 한 수(A)가 다른 수(B)에 포함이 된다면 B에 포함된 A의 바로 뒤 글자(403에서의 3)와 A의 가장 첫 글자를 비교해서 더 큰 것이 우선되게 하자!"였다. 그렇기에 정렬 코드를 아래와 같이 작성하였다.

Arrays.sort(numToStr, (o1, o2) -> {
    if(o1.indexOf(o2) == 0) {
        return Character.compare(o2.charAt(0), o1.charAt(o2.length()));
    }
    else if(o2.indexOf(o1) == 0) {
        return Character.compare(o2.charAt(o1.length()), o1.charAt(0));
    }
    return  o2.compareTo(o1);
});

 

그러나 여기서는 런타임 초과라는 문제가 발생해버렸다. 그렇기에 아예 새로운 방법을 생각할 수 밖에 없었다.

 

문제 해결

생각의 전환이 필요하였다. 여러 개의 코드를 작성했음에도 반례 혹은 런타임 초과가 발생했기 때문이다.

 

해결 방법은 간단했다. "아니 그냥 두 개의 조합을 직접 비교해버릴까?". 정답이었다.

두 개의 조합의 문자열을 비교해서 더 큰 것을 반환하면 되었다.

Arrays.sort(numToStr, (o1, o2) -> -(o1+o2).compareTo(o2+o1));

 

코드 설명

우선 정렬을 위해서 <pre>numbers</pre>을 String 형태의 배열로 바꿔야 했다.

그래서 <pre>numToStr</pre>이라는 배열을 만들어서 옮겨 담았다.

 

그 후 정렬을 하였다. 정렬 코드는 위의 해결 과정에서 다 설명 되었다고 생각한다.

이 후, 반복문을 통해 큰 수로 만들기 위해 정렬된 배열을 차례로 더하였다.

 

여기서부터가 두 번째로 중요한 부분이다.

지금까지에서 만약 [0, 0, 0, 0]가 input으로 들어온다면 결과값은 "0000"이 되어버린다. 그러나 답은 "0"이다.

이를 위해서 앞에 붙은 0을 모두 없애고, 만약 길이가 0이 되어버린다면 답은 "0"이 되도록 하였다.

 

---

코드

import java.util.Arrays;

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

        for(int i = 0 ; i < numbers.length ; i++) {
            numToStr[i] = Integer.toString(numbers[i]);
        }

        Arrays.sort(numToStr, (o1, o2) -> -(o1+o2).compareTo(o2+o1));

        for(String i : numToStr) {
            answer += i;
        }

        answer = answer.replaceAll("^0+", "");
        if(answer.length() == 0) answer = "0";

        return answer;
    }
}

 

---

참고

정규식 설명 : codechacha.com/ko/java-regex/