[PGM_42746] 가장 큰 수 (java)

문제링크

https://programmers.co.kr/learn/courses/30/lessons/42746

코딩테스트 연습 - 가장 큰 수

문제풀이

👨🏻‍💻 핵심 스킬 👨🏻‍💻
 정렬

0과 양의정수의 배열이 주어졌을 때 그 값들을 이어붙여서 가장 크게 만들 수 있는 수를 찾아주는 문제이다.

 

이 문제를 해결하기 위해 배열에 있는 값들을 정렬하여 이어붙이는 방법을 사용하였다. 단순히 오름차순 혹은 내림차순의 정렬이 아니라 문자열의 사전적인 의미의 정렬이 필요하다. 즉 9와 31을 정렬한다면 사전적으로는 9가 더 큰 수 이기 때문에 9를 앞쪽으로 정렬해주는 것이다. 그렇다면 45와 454는 어떻게 정렬해주어야할까? 당연히 45가 앞으로 와 주어야한다. 454가 앞으로 올 경우 45445가 되지만, 45가 앞으로 오는 경우는 45454가 되기 때문이다.

 

이렇게 사전적인 정렬을 하기 위해서는 두 수의 길이를 맞추어주어야한다. 비교할 두 수 o1과 o2가 있다고 하면 o1과 o2의 길이를 맞추어 주어야 적절하게 정렬을 할 수 있다. 두 수중 길이가 작은 수는 다시 앞에서부터 계산해주면 되지 않을까 하지만 그러기에는 굉장히 많은 예외상황이 발생한다. 위에 45와 454도 동일하다. 

 

따라서 자바에서의 String에서의 +연산과 문제 조건에서 1000이하의 수라는 점을 감안하여 o1과 o2를 각각 더하여 숫자가 가장 크게 되는 값을 앞으로 올 수 있도록 정렬하여 문제를 해결해 주었다.

Collections.sort(numberList,
        (o1, o2)-> {
            String front = String.valueOf(o1);
            String back = String.valueOf(o2);
            return Integer.parseInt(front + back) < Integer.parseInt(back + front) ? 1 :
                    Integer.parseInt(front + back) == Integer.parseInt(back + front) ? 0 : -1;
        });

정렬을 해주기 위한 코드이다. o1과 o2를 String으로 변환하고 +연산을 통해 이어붙어기를 해준다. 이 때 (o1+o2) ,(o2+o1)을 해준 후 int로 변환하여 비교해줌으로써 정렬을 해준다. (java8을 배우니 정말 편리한 기능이 많은 것 같다 :)

구현코드

package pgm_42746;

import java.util.*;

public class Solution {
    public String solution(int[] numbers) {

        List<Integer> numberList = new ArrayList<>();
        for(int number : numbers)
            numberList.add(number);

        Collections.sort(numberList,
                (o1, o2)-> {
                    String front = String.valueOf(o1);
                    String back = String.valueOf(o2);
                    return Integer.parseInt(front + back) < Integer.parseInt(back + front) ? 1 :
                            Integer.parseInt(front + back) == Integer.parseInt(back + front) ? 0 : -1;
                });

        String result = "";
        long sum = 0;
        for(int number : numberList){
            result = result + number;
            sum += number;
            sum %= Integer.MAX_VALUE;
        }
        if(sum == 0)
            result = "0";
        return result;
    }
}

잘못된 지식이나 궁금한 내용이 있을 경우 편하게 댓글 남겨주시면 감사하겠습니다 :)