[프로그래머스] Lv.1 정수 내림차순으로 배치하기 - Java

🔥개인 취미 목적으로 프로그래머스 문제를 정리한 게시글입니다.

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

프로그래머스

✏️문제설명

함수 solution은 정수 n을 매개변수로 입력받습니다.

n의 각 자릿수를 큰 것부터 작은 순으로 정렬한 새로운 정수를 리턴해주세요.

예를 들어 n이 118372면 873211을 리턴하면 됩니다.

💡 제한사항

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

📚 입출력 예

n	return
118372	873211

---

💻 소스 코드

import java.util.Arrays;

class Solution {
    public long solution(long n) {
        char[] chars = String.valueOf(n).toCharArray();
        Arrays.sort(chars);
        
        StringBuilder sb = new StringBuilder(chars.length);
        for (char s : chars) {
            sb.append(s);
        }
        
        return Long.parseLong(sb.reverse().toString());
    }
}

 

주어진 코드는 정수 n을 배열로 만들어 큰 숫자 순서대로 재배열하는 함수입니다.

코드의 작동 방식은 다음과 같습니다.

1. String.valueOf(n).toCharArray() 함수를 사용하여 입력된 숫자 n을 문자 배열 chars로 변환합니다.
2. Arrays.sort()를 호출하여 chars 배열을 오름차순으로 정렬합니다.
3. StringBuilder sb = new StringBuilder()를 사용하여 StringBuilder 객체 sb를 생성합니다.
4. sb.reverse().toString()을 호출하여 StringBuilder에 저장된 문자열을 역순으로 만들고, 이를 문자열로 변환합니다.
5. for 루프를 사용하여 chars 배열의 각 문자를 sb에 추가합니다.
6. Long.parseLong()을 호출하여 역순으로 만들어진 문자열을 다시 정수 long으로 변환하고, 이를 반환합니다.

이 코드는 입력된 숫자의 각 자릿수를 재배열하여 만들 수 있는 가장 큰 숫자를 찾는 효율적인 방법을 제공합니다.

시간 복잡도

1. 숫자를 문자열로 변환 (String.valueOf(n)) : 이 연산의 시간 복잡도는 입력 숫자 n의 자릿수에 비례합니다. 숫자의 자릿수를 d라고 하면, 이 연산의 시간 복잡도는 O(d)입니다.
2. 문자 배열로 변환 (toCharArray()) : 문자열의 길이에 비례하는 시간이 소요되므로, 이 연산의 시간 복잡도도 O(d)입니다.
3. 배열 정렬 (Arrays.sort(chars)) : Java의 Arrays.sort() 메소드는 Dual-Pivot Quicksort 알고리즘을 사용하며, 평균적으로 O(d log d)의 시간 복잡도를 가집니다.
4. 문자열 빌드 및 역순 (StringBuilder 및 reverse()) : 이 부분의 시간 복잡도는 O(d)입니다. 각 문자를 StringBuilder에 추가하는 데는 O(1)의 시간이 걸리며, 총 d개의 문자가 있으므로 O(d)가 되고, reverse() 메서드도 O(d)의 시간이 소요됩니다.

따라서, 전체 시간 복잡도는 각 단계의 시간 복잡도를 합한 것입니다: O(d) + O(d) + O(d log d) + O(d) = O(d log d) (가장 큰 항이 결정적인 역할을 합니다).

공간 복잡도

1. 문자 배열 (char[] chars): 숫자 n의 각 자릿수를 저장하는 데 사용되므로 공간 복잡도는 O(d)입니다.
2. StringBuilder 객체: 이 객체는 최대 d개의 문자를 저장할 수 있어야 하므로, 공간 복잡도는 O(d)입니다.

결과적으로, 전체 공간 복잡도는 O(d)입니다. 여기서 d는 입력 숫자 n의 자릿수를 나타냅니다.