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

문제 링크

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

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

 

정수를 이어 붙여 가장 큰 수를 만들기 위해서는 맨 앞자리의 숫자가 중요하다.

만약 앞자리의 숫자가 같다면 그 다음 숫자의 크기가 중요할 것이다.

 

ex) [3, 30, 34, 5, 9] 프로그래머스 예제

3과 30을 두고 보면 3을 앞에 두는게 더 좋을 것이다. 330 vs 303

허나 3과 34는 34를 앞에 두는게 더 좋다. 343 vs 334

 

숫자를 비교하기에는 서로 자릿수가 다를 경우들이 존재한다.

따라서 필자가 처음 생각해낸 방법은 '자릿수를 맞춰주는'것이다.

최대 자리수는 1000 <- 4자리 이기 떄문에 남은 자릿수를 맨 앞숫자로 맞춰주는 것이다.

위의 예제로 사용하면 

3333 3033 3433 5555 9999

이렇게 만들고 정렬하면 이어 붙일 때 가장 큰 순서대로 알 수 있게 된다!

 

따라서 HashMap<해당 숫자의 원래 index, 자릿수를 맞춰 변형한 숫자>에 값을 넣어두고 정렬하면.

<9999, 4> <5555, 3> <3433, 2> <3333, 0> <3033, 1> 순서대로 정렬된다.

value값의 index를 이용해서 해당 index 순으로 이어붙이면 완성이다.

9 + 5 + 34 + 3 + 30 = 9534330

 

다만, 10 101의 경우 둘다 1011이 되는 문제점이 발생했다.

이러한 문제를 방지하기 위해 2자리 수는 자기 자신을 그대로 복사하여 자릿수를 맞춰주도록 했다.

1010 1011

 

import java.util.List;
import java.util.LinkedList;
import java.util.HashMap;
import java.util.Map;
import java.util.Comparator;
import java.util.Collections;
import java.util.ArrayList;

class Solution {
    public String solution(int[] numbers) {
        String answer = "";
        HashMap<Integer, Integer> map = new HashMap<>();
        String [] nums = new String[numbers.length];
        String num;
        
        for (int i = 0; i < numbers.length; i++) {
            nums[i] = Integer.toString(numbers[i]);
        }
        for (int i = 0; i < nums.length; i++) {
            num = nums[i];
            if (num.length() == 2)
                num += num;
            else {
                for (int j = num.length(); j != 4; j++) {
                    num += nums[i].charAt(0);
                }
            }
            map.put(i, Integer.parseInt(num));
        }
        
        // 해시 맵 정렬 (key 기준으로) 
        List<Map.Entry<Integer, Integer>> entryList = new LinkedList<>(map.entrySet());
        entryList.sort(new Comparator<Map.Entry<Integer, Integer>>() {
            @Override
            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
	        return o2.getValue() - o1.getValue();
            }
        });
        
        for (Map.Entry<Integer, Integer> entry : entryList) {
            answer += nums[entry.getKey()];
        }
        if (answer.charAt(0) == '0')
					return "0";
        return answer;
    }
}