[프로그래머스] 정렬 Level 2. 가장 큰 수(JAVA)

일단 푸는데 엄청 오래 걸렸다.

[3, 30, 34] 같은 케이스를 [34, 3, 30]으로 정렬해야했기에 단순 비교도, char[]로 변환해 자릿수 별로 비교하는 방법도 어려웠다.

고민끝에 나온 첫번째 아이디어는
원소 크기가 최대 1000 이하라는 점을 이용해서 전부 3자리로 맞춰서 비교하는 방법이었다.

빈 자릿수는 전부 마지막 숫자로 채울 경우 원하는 방식으로 정렬이 가능했다.

3    → 3333 

30  → 3000

34  → 3444

변환한 3자리 값을 key, 원본 값을 value로 넣고 TreeMap으로 구현하면 정렬도 따로 해줄 필요 없을 것 같았다.

 

코드

import java.util.*;
class Solution {
    public String solution(int[] numbers) {
        String answer = "";
        Map<Integer, Integer> numMap = new TreeMap<Integer, Integer>();
        for(int number : numbers){
        int keyNum = number;
            if(keyNum > 0){
                int lastNum = keyNum % 10;
                while(keyNum < 100){
                    keyNum = (keyNum * 10) + lastNum;
                }
            }
            numMap.put(keyNum, number);
        }
        for(int key : numMap.keySet()){
            answer = numMap.get(key).toString() + answer;
            
        }
        return answer;
    }
}

결과

실패가 우수수 떨어졌다.

일단 동일한 숫자가 중복될 경우에 대한 대비가 안됐다.

또한 9와 99, 999를 같은 값으로 인식했다.

동일한 숫자 중복은 숫자 별로 카운팅한 또다른 해시맵으로 구현한다하더라도,

9와 99를 구분하지 못하는 문제는 해결이 어려울듯 싶었다.

---

지난번에 사용헀던 merge sort를 좀 개량해서 무식하게 비교해보기로 했다.

자릿수를 맞춰서 비교하는 방식을 폐기하고  a+b 값과 b+a를 비교했다.

 

코드

import java.util.*;
class Solution {
    public String solution(int[] numbers) {
        String answer = "";
        String[] newArray = {};
        newArray = mergeSort(numbers);
        
        if(newArray[0].equals("0")) return "0"; //{0,0,0,0} 방지
        
        for(String s : newArray){
           answer += s;
        }
        return answer;
        
    }
    
    public String[] mergeSort(int[] array){
        if (array.length < 2){
            String[] newArray = {Integer.toString(array[0])};
            return newArray;
        }
        int arrayLength = array.length;
        String[] lowArray = mergeSort(Arrays.copyOfRange(array, 0, array.length/2));
        String[] highArray = mergeSort(Arrays.copyOfRange(array, array.length/2, array.length));
        String[] mergeArray = new String[array.length];
        int low = 0;
        int high = 0;
        int merge = 0;
        while(low < lowArray.length && high < highArray.length){
            int compare = (lowArray[low]+highArray[high]).compareTo(highArray[high]+lowArray[low]);
            if(compare >=1)
                mergeArray[merge++] = lowArray[low++];
            else
                mergeArray[merge++] = highArray[high++];
        }
        while(low < lowArray.length){
            mergeArray[merge++] = lowArray[low++];
        }
        while(high < highArray.length){
            mergeArray[merge++] = highArray[high++];
        }
        return mergeArray;
    }
}

 

결과

성능이 느린거 아닌가 싶었지만 전부 통과는 했고, 점수도 11점을 받았다.

함수를 직접 구현할수록 높은 점수를 주는 것 같다.

 

테스트케이스 11번이 계속 실패했는데, 입력값이 {0,0,0,0} 일때 결과값이 0000으로 나와서 그런거였다.

if(newArray[0].equals("0")) return "0";

위 코드로 예외 처리를 해주었다.

---

다른 사람의 풀이에서 좋아요를 가장 많이 받은 풀이를 가져와봤다.

 

코드

import java.util.*;

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

        List<Integer> list = new ArrayList<>();
        for(int i = 0; i < numbers.length; i++) {
            list.add(numbers[i]);
        }
        Collections.sort(list, (a, b) -> {
            String as = String.valueOf(a), bs = String.valueOf(b);
            return -Integer.compare(Integer.parseInt(as + bs), Integer.parseInt(bs + as));
        });
        StringBuilder sb = new StringBuilder();
        for(Integer i : list) {
            sb.append(i);
        }
        answer = sb.toString();
        if(answer.charAt(0) == '0') {
            return "0";
        }else {
            return answer;
        }
    }
}

결과

오... 깔끔하다. 성능도 눈에 띄게 향상됐다.

무엇보다 StringBuilder를 사용한 부분이 맘에 들었다.

내 풀이에서도 StringBuilder를 적용했더니 1000ms가 넘어가던 테스크 케이스들의 수행시간이 1/5이상 감소했다.

 

sort 부분에서 String으로 변환한 숫자들을 다시 Integer로 변환해서 비교하길래

String 상태에서 비교하는 것과 성능 차이가 있나싶어서 테스트해봤더니 딱히 유의미한 차이는 없었다.