[정렬] 프로그래머스 level 2 가장 큰 수 python, java 풀이

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

 

처음 떠올린 생각은..

1. 순열을 써서 가능한 모든 문자열 조합을 나열하고

2. 그걸 싹다 int로 바꿔서 sort 시켜주기

3. 다시 문자열로 바꾸기

아무리 봐도 비효율적인 것 같아서 고민해보다가 구글에 찾아봤다.

 

해결 흐름

1. int 배열을 모두 string으로 변환

2. 문자열에 sort를 한다. 이때 문자열에 sort를 적용하면 사전식 배열을 하게 되는데, 이는 각 문자의 ASCII 코드 값에 따라 정렬하는 방식을 의미한다. 즉, 문자열의 첫 번째 문자부터 비교하며 정렬하고, 첫 번째 문자가 동일한 경우 두 번째 문자를 비교하고, 두 번째 문자도 동일한 경우 세 번째 문자를 비교하며 이어가는 방식이다.

 

문제는

3, 30, 34, 5, 9 의 경우

9, 5, 34, 30, 3이 되는데

9534303 보다 9534330이 크므로

30과 3을 어떻게 비교해주냐..

 

python 풀이를 보면 *3을 해주어 303030과 333으로 변환하고, 303과 333에서 333이 더 크므로

9, 5, 34, 3, 30 을 만든다

 

java 풀이로는 compareTo를 사용한다. compareTo는 문자열 비교를 할 때 사전식으로 비교를 해주기 때문이다.

앞에 문자열과 뒤 문자열을 붙여주어 두 값을 비교한다.

예를 들어 o1 = "30" ,o2 = "3"의 경우 "30"+"3" = "303", "3" + "30" = "330"가 되니,

o2+o1일 때 (o2가 왼쪽일 때)비교한 값이 더 크므로 "3"이 "30"보다 왼쪽에 있게 된다.

이러한 논리로 9, 5, 34, 3, 30 을 만든다

 

Python 코드

def solution(numbers):
    numbers = list(map(str, numbers))
    numbers.sort(key=lambda x: x * 3, reverse=True)
    return str(int(''.join(numbers)))

Java 코드

import java.util.Arrays;

class Solution {
    public static String solution(int[] numbers) {
        // Convert int[] to String[].
        String[] strArray = Arrays.stream(numbers)
            .mapToObj(String::valueOf)
            .toArray(String[]::new);

        // Compares two strings lexicographically.
        Arrays.sort(strArray, (o1, o2) -> (o2 + o1).compareTo(o1 + o2));

        String answer = String.join("", strArray);
        return (answer.charAt(0) == '0') ? "0" : answer;
    }
}