문제 개요
요소들로 이루어진 배열 nums가 주어졌을 때, 이를 비내림차순으로 정렬하는 문제를 생각해 보겠습니다. 다만 여기서 사용하는 정렬 방식은 무작위(randomized) 기법입니다. 배열이 이미 정렬되어 있는지 검사하고, 정렬되어 있지 않다면 요소들을 무작위로 섞은(shuffle) 뒤 다시 검사합니다. 이 과정을 배열 전체가 정렬될 때까지 반복하며, 우리가 구해야 할 것은 정렬이 완성될 때까지 필요한 셔플 횟수의 기댓값입니다. 결과는 소수점 여섯째 자리까지 반올림하여 출력합니다.
접근 방식
핵심 아이디어는 간단합니다. 서로 다른 n개의 요소로 만들 수 있는 순열은 총 n!가지이며, 그중 정렬된 상태는 단 하나뿐입니다. 따라서 한 번의 무작위 셔플로 정렬된 배열이 나올 확률은 1/n!이고, 기하분포의 성질에 따라 기대 시도 횟수는 그 역수, 즉 n!이 됩니다.
예를 들어 입력이 nums = [5, 2, 7]이라면 세 요소의 순열은 총 3! = 6가지이고, 이 중 정확히 하나만 정렬된 상태입니다. 따라서 정렬된 배열이 나올 때까지 필요한 셔플 횟수의 기댓값은 6이 됩니다.
배열에 중복된 값이 있다면 어떨까요? 중복을 고려한 고유 순열의 개수는 n!을 각 값별 등장 횟수의 팩토리얼로 나눈 값입니다. 예를 들어 [1, 1, 2]라면 고유 순열은 3! / (2! × 1!) = 3가지이므로 기댓값은 3입니다. 이 공식이 바로 코드에서 분자(num)와 분모(den)로 표현되는 부분입니다.
알고리즘 단계
- 정렬 여부 확인: nums가 이미 정렬되어 있다면 0을 반환합니다. 셔플이 전혀 필요하지 않기 때문입니다.
- 등장 횟수 집계: 그렇지 않다면 빈 딕셔너리 m을 만들어 각 값이 몇 번 나타나는지 센다.
- 분자 계산: num := 1로 초기화한 뒤, m의 각 키 i에 대해 num := num × factorial(m[i])를 적용합니다. 이는 중복 요소로 인한 중복 순열을 보정하는 역할을 합니다.
- 분모 계산: den := factorial(len(nums))로 전체 순열의 수를 구합니다.
- 결과 반환: den ÷ num을 소수점 여섯째 자리까지 반올림하여 반환합니다.
구현 예제
from math import factorial
def solve(nums):
# 이미 정렬되어 있으면 셔플 불필요
if nums == sorted(nums):
return 0
else:
# 각 값의 등장 횟수를 집계
m = {}
for i in nums:
if i in m:
m[i] += 1
else:
m[i] = 1
# 중복 순열 보정용 분자
num = 1
for i in m:
num *= factorial(m[i])
# 전체 순열의 수
den = factorial(len(nums))
return round(den / num, 6)
nums = [5, 2, 7]
print(solve(nums))입력
[5, 2, 7]
출력
6.0
마무리
이 알고리즘은 무작위 셔플 정렬(보고소트 계열)의 기대 비용을 수학적으로 계산하는 방법을 보여줍니다. 실무에서 결코 사용하지 않는 비효율적인 정렬이지만, 순열 counting과 기하분포의 기댓값 공식(E = 1/p)을 학습하기에는 아주 좋은 예제입니다. 배열 길이가 커질수록 기댓값이 팩토리얼 단위로 폭발적으로 증가한다는 점도 흥미로운 포인트입니다.