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

굉장히 쉽다고 생각했지만 생각보다 굉장히 오래걸린 풀이...

numbers	sort	return
[2, 23, 231]	23 231 2	232312
[3, 321, 32]	3 32 321	332321
[3, 312, 31]	3 31 312	331312

위 처럼 다양한 경우에 따라 정렬이 달라져야 하는데,

 

처음에생각한 방법은 number의 원소는 최대 1000 이므로 첫번째자리의 숫자로 오른쪽을 다 채운다음 단순정렬.

numbers	rpad	sort	return
[2, 23, 231]	[2(22), 23(2), 231]	[23(2), 231, 2(22)]	232312
[3, 321, 32]	[3(33), 321, 32(3)]	[3(33), 32(3), 321]	332321
[3, 312, 31]	[3(33), 312, 31(3)]	[3(33), 31(3), 312]	331312

된다. 되긴 되는데... 속도가 안나온다.

rpad를 하기위해 아래와 같이 4자리를 빈칸으로 채우고 빈칸을 다시 첫번째 자리로 치환하는 과정에서 부하가 걸린다.

String.format("%-4s", o1).replace(" ", o1.substring(0,1));

생각을 바꿔서 차라리 앞뒤로 일단 붙여보고 어떤게 더 큰지 판단해서 정렬하자.

 

아마도 테스트 케이스의 마지막은 순수 0으로 되어 있는 케이스인 것 같으니, 정렬하고 제일 큰값이 0이면 그냥 0을 리턴하도록 하자.

import java.util.*;

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

        for (int i = 0; i < numbers.length; i++) {
            int number = numbers[i];
            strs[i] = String.valueOf(number);
        }
        
        Arrays.sort(strs, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return ((o2+o1).compareTo(o1+o2));
            }
        });
        
        if(strs[0].equals("0")) {
            return "0";
        }
        
        for (String str : strs) {
            answer += str;
        }
        return answer;
    }
}

---

+ 최초 string 반복으로 안되는 케이스가 있다.
[10, 101] 의 return은 [10110] 이 나와야 하지만 [10(1), 101] 로 정렬하면 [10101] 이 나올수도 있기 때문에
원소 자신을 반복해서 채우는게 맞다.
[10(10), 101(1)] 의 return은 [10110]

따라서 그냥 자기자신을 반복해서 채우고(1자리수를 기준으로 2번 더 채운다) 비교하는것도 가능함.

import java.util.*;

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

        for (int i = 0; i < numbers.length; i++) {
            int number = numbers[i];
            strs[i] = String.valueOf(number);
        }

        Arrays.sort(strs, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                String o1c = o1.concat(o1).concat(o1);
                String o2c = o2.concat(o2).concat(o2);
                return o2c.compareTo(o1c);
            }
        });

        if(strs[0].equals("0")) {
            return "0";
        }

        for (String str : strs) {
            answer += str;
        }

        return answer;
    }
}

 

출처: 프로그래머스 코딩 테스트 연습, 
https://programmers.co.kr/learn/challenges