[BOJ/백준] 9742 순열 - 파이썬

문제

https://www.acmicpc.net/problem/9742

9742번: 순열

 

 

문제풀이

bruteforce 문제

-찾고자 하는 순서가 문자열의 팩토리얼 값 보다 클 때, no permutation 출력

-그렇지 않은 경우 solve함수 재귀적으로 호출

 solve 함수

 문자열의 길이가 입력받은 문자열과 같고, 원하는 순서의 문자열일때까지 반복한다. 

 solve(s+k,i+1) 으로 문자를 추가하고 문자열 길이를 늘려주면서 재귀적으로 호출

 

 

 

코드

import sys
input=sys.stdin.readline
import math

def solve(s,i):
    global cnt
    if i==len(string):
        cnt+=1
        if cnt==n:
            return s
    else:
        for k in string:
            if k not in s:
                res=solve(s+k,i+1)
                if res:
                    return res
    return
    
while(True):
    cnt=0
    inn=input().split()
    
    if len(inn)!=2:
        break
    string,n=inn
    n=int(n)
    many=math.factorial(len(string))
    if n>many:
        print(string,n,'= No permutation')
        continue
    print(string,n,'=',solve('',0))