[Java] 정수 내림차순으로 배치하기

문제 설명

함수 solution은 정수 n을 매개변수로 입력받습니다. n의 각 자릿수를 큰것부터 작은 순으로 정렬한 새로운 정수를 리턴해주세요. 예를들어 n이 118372면 873211을 리턴하면 됩니다.

 

 

제한 조건

• n은 1이상 8000000000 이하인 자연수입니다.

 

입출력 예

n : 118372

return : 873211

 

---

 

 

알고리즘에 대해 생각해보자면

1. n을 문자열로 반환해준다.
2. 문자열을 배열로 반환해준다.
3. 자릿수를 내림차순으로 정렬한다.
4. 정렬된 자릿수를 문자열로 결합한다.
5. 결합된 문자열을 long으로 변환하여 answer에 저장한다.

 

이 순으로 진행하면 될 것 같다.

 

 

 

아직 형변환에 대한 메소드를 잘 알고 있지 못해서 구글의 도움을 받았다.

// 숫자를 문자열로 변환  
String str = Long.toString(n);  

// 문자열을 문자 배열로 변환  
char[] digits = str.toCharArray();

// 정렬된 자릿수를 문자열로 결합  
StringBuilder sortedString = new StringBuilder();  
for (char digit : digits) {  
    sortedString.append(digit);  
}

// 문자열을 long으로 변환하여 answer에 저장  
answer = Long.parseLong(sortedString.toString());

이 코드들을 이용하면 된다.

 

 

 

 

 

모든 코드를 조합하면

class Solution {  
    public long solution(long n) {  
        long answer = 0;  

        // 숫자를 문자열로 변환  
        String str = Long.toString(n);  

        // 문자열을 문자 배열로 변환  
        char[] digits = str.toCharArray();  

        // 입력 범위 확인  
        if (1 <= n && n <= 8000000000L) {  
            // 자릿수를 내림차순으로 정렬  
            for (int i = 0; i < digits.length - 1; i++) {  
                for (int j = i + 1; j < digits.length; j++) {  
                    if (digits[j] > digits[i]) { // 내림차순 비교  
                        // Swap  
                        char temp = digits[i];  
                        digits[i] = digits[j];  
                        digits[j] = temp;  
                    }  
                }  
            }  

            // 정렬된 자릿수를 문자열로 결합  
            StringBuilder sortedString = new StringBuilder();  
            for (char digit : digits) {  
                sortedString.append(digit);  
            }  

            // 문자열을 long으로 변환하여 answer에 저장  
            answer = Long.parseLong(sortedString.toString());  
        }  

        return answer;  
    }  

    public static void main(String[] args) {  
        Solution solution = new Solution();  

        long input = 118372; // 입력 값  
        long output = solution.solution(input); // 솔루션 함수 실행  

        // 결과 출력  
        System.out.println(output);  
    }  
}

이렇게 하면 정상적으로 결과가 출력된다.

최대한 내장 함수를 사용하지 않고 알고리즘을 풀어서 코딩하려고 노력하였다.

그리고 내장 함수를 이용한 간단한 코드를 GPT에게 물어보았다.

아래는 GPT가 반환한 간단한 코드이다.

import java.util.Arrays;  

class Solution {  
    public long solution(long n) {  
        // 숫자를 문자열로 변환 -> 문자 배열로 변환 -> 정렬 및 내림차순 변환 -> 문자열로 결합 후 숫자로 변환  
        String sorted = Arrays.stream(Long.toString(n).split(""))  
                              .sorted((a, b) -> b.compareTo(a)) // 내림차순 정렬  
                              .reduce("", String::concat); // 문자열로 결합  

        return Long.parseLong(sorted); // 문자열을 long으로 변환하여 반환  
    }  

    public static void main(String[] args) {  
        Solution solution = new Solution();  

        long input = 118372; // 입력 값  
        long output = solution.solution(input); // 솔루션 함수 실행  

        // 결과 출력  
        System.out.println(output); // 출력: 873211  
    }  
}

아래 설명이 GPT가 반환한 설명이다.

코드 설명

1. Long.toString(n)

• 주어진 숫자 n을 문자열로 변환합니다.

2. .split("")

• 문자열을 각 자릿수별로 나누어 문자열 배열로 만듭니다.

3. Arrays.stream()

• 배열을 스트림으로 변환하여 간단히 정렬 및 변환 작업을 수행합니다.

4. .sorted((a, b) -> b.compareTo(a))

• 정렬을 수행하며, **b.compareTo(a)**를 사용하여 내림차순으로 정렬합니다.

5. .reduce("", String::concat)

• 정렬된 문자열 배열의 요소들을 하나씩 결합하여 최종 문자열로 만듭니다.

6. Long.parseLong(sorted)

• 최종 문자열을 숫자로 변환하여 반환합니다.

---

소스코드 실행 결과

• 입력값: 118372
• 출력 결과: 873211

---

코드에 대한 결론

위 코드는 가장 간단하면서도 파이썬 스타일의 코드 직관성을 자바(Java)로 표현한 방식입니다.
Long.toString()과 Arrays.stream() 등 내장 메서드를 최대한 활용하여 가독성과 효율성을 높였습니다.

 

 

 

그리고 코딩연습 사이트에서 다른 사람들의 풀이 중 가장 좋아요 수가 많은 코드를 살펴보았다.

public class ReverseInt {
    String res = "";
    public int reverseInt(int n){
        res = "";
        Integer.toString(n).chars().sorted().forEach(c -> res = Character.valueOf((char)c) + res);
        return Integer.parseInt(res);
    }

    // 아래는 테스트로 출력해 보기 위한 코드입니다.
    public static void  main(String[] args){
        ReverseInt ri = new ReverseInt();
        System.out.println(ri.reverseInt(118372));
    }
}

 

 

 

코드 비교: 시간 복잡도 분석

첫 번째 코드는 내가 쓴 코드이고, 두 번째 코드는 GPT가 반환한 코드, 세 번째 코드는 좋아요 수가 가장 많던 코드이다.

이 코드들의 시간 복잡도를 상대적으로 비교한 표가 아래 보이는 것이다.

내장 함수를 이용한 코드가 절대적으로 빨랐고 세 번째 코드가 최악의 상황이 아니라면 미묘하게 더 효율적이었다.

첫 번째 코드	버블 정렬	문자 배열의 정렬 및 교환	O(n²)	비효율적인 버블 정렬 사용. 작은 입력에서는 괜찮지만, 큰 입력에서는 성능 저하.
두 번째 코드	Timsort (sorted())	문자열 배열로 분리 및 정렬	O(n log n)	내장 정렬 알고리즘 활용, 가장 효율적이며 가독성도 높음.
세 번째 코드	Timsort (sorted())	문자 결합 과정에서 문자열 사용	O(n²)	문자열 결합(res = res + c)이 반복적으로 수행되어 성능 저하