[프로그래머스] 정수 내림차순으로 배치하기

문제 설명
주어진 자연수 n의 각 자릿수를 큰 순서대로 정렬하여 새로운 정수를 반환하는 문제입니다. 예를 들어, n = 118372라면, 각 자릿수를 내림차순으로 정렬한 후, 873211을 반환해야 합니다.

---

제한 조건

• n은 1 이상 8,000,000,000 이하인 자연수입니다.

---

입출력 예

n	return
118372	873211

---

문제 풀이

이 문제는 다음 순서대로 해결할 수 있습니다:

1. 정수 n을 문자열로 변환합니다.
2. 문자열의 각 자릿수를 리스트에 저장한 후, 이를 내림차순으로 정렬합니다.
3. 정렬된 리스트를 다시 문자열로 합치고, 이를 정수로 변환하여 반환합니다.

1. Python 코드 풀이

def solution(n):
    # 정수를 문자열로 변환한 뒤, 각 자릿수를 리스트로 변환하고 내림차순으로 정렬
    sorted_digits = sorted(str(n), reverse=True)

    # 정렬된 자릿수를 하나의 문자열로 합친 후, 다시 정수로 변환
    return int(''.join(sorted_digits))

# 테스트 예시
print(solution(118372))  # 출력: 873211

코드 설명

1. str(n)을 사용하여 정수 n을 문자열로 변환합니다.
2. sorted() 함수를 이용해 문자열의 각 자릿수를 리스트로 변환하고, reverse=True로 설정하여 내림차순으로 정렬합니다.
3. ''.join()을 사용해 정렬된 리스트를 다시 문자열로 합칩니다.
4. 마지막으로 int()를 이용해 이 문자열을 정수로 변환하여 반환합니다.

---

2. Java 코드 풀이

import java.util.Arrays;
import java.util.Collections;

class Solution {
    public long solution(long n) {
        // 정수를 문자열로 변환한 후, 각 자릿수를 배열에 저장
        String[] digits = Long.toString(n).split("");

        // 배열을 내림차순으로 정렬
        Arrays.sort(digits, Collections.reverseOrder());

        // 정렬된 배열을 하나의 문자열로 합치고, 이를 다시 long 타입으로 변환
        String sortedStr = String.join("", digits);

        return Long.parseLong(sortedStr);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.solution(118372));  // 출력: 873211
    }
}

코드 설명

1. Long.toString(n)을 사용하여 정수 n을 문자열로 변환하고, split("")을 이용해 각 자릿수를 배열에 저장합니다.
2. Arrays.sort()와 Collections.reverseOrder()를 사용하여 배열을 내림차순으로 정렬합니다.
3. String.join("", digits)를 사용해 정렬된 배열을 하나의 문자열로 합칩니다.
4. 마지막으로 Long.parseLong()을 사용해 문자열을 다시 정수로 변환하여 반환합니다.

---

3. 시간 복잡도 분석

• Python:

  • sorted() 함수는 Timsort 알고리즘을 사용하며, 시간 복잡도는 O(d log d)입니다. 여기서 d는 숫자의 자릿수입니다.
  • 주어진 문제에서 n은 최대 10자리 숫자이므로, 시간 복잡도는 매우 효율적입니다.

• Java:

  • Arrays.sort()는 Dual-Pivot Quicksort를 사용하여, 시간 복잡도는 O(d log d)입니다. d는 자릿수입니다.

---

결론

이 문제는 주어진 정수 n을 문자열로 변환하여, 자릿수를 내림차순으로 정렬한 후 다시 정수로 변환하는 방식으로 해결할 수 있습니다. Python과 Java 모두 정렬을 위한 표준 라이브러리를 사용해 효율적으로 문제를 해결할 수 있으며, 시간 복잡도는 O(d log d)로 자릿수에 비례합니다.