순열

2020-12-23 
layout: post
title: "백준 9742 - 순열"
author: "asadal"
tags: ["python", "파이썬", "백준", "순열", "permutations", "factorial"]

서로 다른 숫자와 문자로 이뤄진 집합과 위치가 주어졌을 때, 그 집합의 순열 중 주어진 위치의 순열을 구하는 프로그램.

import sys
for i in sys.stdin:
    a, b = i.split() # 'bein', 20
    print(a, b, '=', end=' ')
    f, b = 1, int(b)-1
    for i in range(len(a)):
        f *= i + 1 # 전체 순열의 수(4!=24) 구하기(f = 24, b = 19)
    if f <= b: # b가 전체 순열 수보다 많을 경우
        print('No permutation')
        continue
    for i in range(len(a), 0, -1): 
        # 문자열(abcd)을 뒤에서부터 탐색(i = 4, 3, 2, 1)
        f //= i # f = 6, 2, 1, 1
        print(a[b//f], end='') # a[0], a[0], a[1], a[0]
        a = a[:b//f] + a[b//f+1:] # bei, ei, e
        b %= f # 1, 1, 0, 0
    print()

문제 보기