[프로그래머스] 가장 큰 수(java)

문제 설명

정수형 문자열이 담긴 배열이 주어진다. 이때 정수형들을 조합해서 제일 큰 수를 문자열로 반환하는 문제이다. 이때 조합한다는 것의 의미는 더한다는 게 아니라 붙여준다라는 의미로 해석하면 될 듯 싶다.

https://school.programmers.co.kr/learn/courses/30/lessons/42746?language=java

프로그래머스

문제 풀이

문제를 보면 알겠지만, 단순히 정수들을 정렬해서 이를 문자열로 만들어주면 안 된다.

첫 번째 예시의 경우 주어진 문자열은 [6, 10, 2]이다. 이를 정수형으로 정렬해서 문자열로 만들어 주면 1062로 정답보다 훨씬 작은 수가 된다.

 

즉, 제일 첫 번째 숫자끼리 비교해서 더 큰 수를 앞쪽에 붙여주는 방식으로 문제를 풀어야 한다.

 

그렇다면 이를 어떻게 해결하면 좋을까?

 

해결 방법은 의외로 간단한데 정수들을 문자로 바꿔서 비교해주는 것이다. 문자로 바꿔서 비교해주면 각 문자의 인덱스 별로 비교가 가능하니, 첫 번째 숫자끼리 비교해서 더 큰 수가 앞에 올 수 있는 것이다.

 

예시로 6과 10이 있다고 하자. 이를 정수형으로 비교해 내림차순으로 정렬하면 [10, 6]이 된다. 하지만, 문자형으로 변환해서 내림차순 정렬을 하면 6의 첫 번째 인덱스 값은 6, 10의 첫 번째 인덱스 값은 1이니 결과는 [6, 10]이 나온다. 

 

좋다! 그러면 문자형으로 변환해서 내림차순으로 정렬해주면 끝일까?

답은 아니. 아직 할 것이 더 남았다.

 

만일 3과 30이 주어졌다고 하자. 위의 논리대로 정렬을 하면 값은 303이 나와서 문제를 틀리게 된다.

왜일까? 자바에서는 숫자 문자열을 정렬할 때 자릿수가 큰 값을 더 크게 보기 때문이다.

 

그러므로 단순히 정렬을 해주지 말고 두 개의 문자열을 더해준 다음에 비교를 해줘야 한다.

위의 3과 30을 다시 생각해보자. 두 문자열을 더하는 경우는 "330"과 "303"이 존재한다. 이때 내림차순 정렬을 해주면 자연스럽게 330이 반환된다. 이러한 원리로 나온 코드가 아래와 같다.

        Collections.sort(sortAnswer, (o1, o2) -> {
            return (o2+o1).compareTo(o1+o2);
        });

 

또한 "0"이 맨 앞에 있을 경우 해당 값들은 모두 0이니까 "0"을 반환해준다. 안 그러면 "000..." 문자열이 되서 숫자가 아니게 된다. 아무튼 그리고 join을 활용해서 문자열을 붙여 반환하면 된다.

코드

java

import java.util.*;

class Solution {
    public String solution(int[] numbers) {
        String answer = "";
        List<String> sortAnswer = new ArrayList<>();
        
        for (int number : numbers) {
            sortAnswer.add(Integer.toString(number));
        }
        Collections.sort(sortAnswer, (o1, o2) -> {
            return (o2+o1).compareTo(o1+o2);
        });
        
        if(sortAnswer.get(0).equals("0")) {
            return "0";
        }
        
        return String.join("", sortAnswer);
    }
}