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

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

책 구매하기

문제 정보

• 분류: 정렬
• 정답률: 87%
• 권장 시간 복잡도: O(D log D)
• 핵심 키워드: 문자열 변환, 내림차순, 정렬, 자리수
• 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/12933

문제를 읽을 때 체크할 포인트

숫자를 자릿수 문자로 바꿔 정렬한 뒤 다시 합치면 끝나는 문제다. 구현 난이도는 낮지만, 문자열과 정수 변환 흐름을 깔끔하게 가져가면 실수가 없다.

정렬 문제는 손이 바빠지기 전에 비교 기준부터 정리하는 게 먼저다. 어떤 값을 기준으로 한 번만 정렬하면 그다음 오히려 짧아지는 경우가 많다.

풀이 흐름

1. 정수를 문자열로 바꿔 각 자릿수를 분리한다.
2. 내림차순 정렬한다.
3. 다시 이어 붙여 정수로 바꾼다.

구현할 때 놓치기 쉬운 부분

숫자를 문자로 바꿔 내림차순 정렬하면 되는 문제다. 자리수를 직접 쪼개서 비교하려고 들면 코드만 길어지고 실수할 지점이 늘어난다.

파이썬 정답 코드

def solution(n):
  # 정수를 문자열로 바꿔 각 자릿수를 분리한다.
  return int("".join(sorted(str(n), reverse=True)))

시간 복잡도

D는 자릿수 개수이다.

자릿수 D개를 문자나 배열로 바꾼 뒤 정렬한다. 자릿수만 정렬하면 되므로 핵심 비용은 D개 정렬 비용인 O(D log D)이다.

따라서 시간 복잡도는 O(D log D)이다.