BOJ 9742번 - 순열 (파이썬)

문제

---

집합의 순열이란 집합의 서로 다른 원소를 모두 사용해 만들 수 있는 순서이다. 예를 들어, {2,3,5}의 순열은 다음과 같다.

1. 2 3 5
2. 2 5 3
3. 3 2 5
4. 3 5 2
5. 5 2 3
6. 5 3 2

각각의 순열은 숫자로 나타낼 수 있다. 위의 순열은 사전순으로 쓰여져 있으며, 등장하는 순서를 이용해 나타낸다. 즉, 3 5 2는 위치 4에 있고, 5 3 2는 마지막 위치인 6에 있다.

{b,e,i,n}으로 만들 수 있는 순열은 다음과 같다.

1. b e i n
2. b e n i
3. b i e n
4. b i n e
5. b n e i
6. b n i e
7. e b i n
8. e b n i
9. e i b n
10. e i n b
11. e n b i 
12. e n i b
13. i b e n
14. i b n e
15. i e b n
16. i e n b
17. i n b e
18. i n e b
19. n b e i
20. n b i e
21. n e b i
22. n e i b
23. n i b e
24. n i e b

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

 

접근법

---

일단 문제를 읽고서 완전탐색 문제라고 생각하고 재귀함수를 어떻게 구성할지 생각을 하는 방식으로 접근했다.

해당하는 순열이 없는 경우는 어떻게 구현할까 생각을 하다가 다른 풀이를 참고해서 구현했다. factorial함수를 사용해서 주어진 문자열의 길이의 순열의 수보다 b가 더 크다면 해당 순열이 없는 것으로 간주하였다.

 

풀이

---

import sys

input=sys.stdin.readline

def dfs(string,num,letter):
    global cnt
    if len(string)==len(letter):
        cnt+=1
        if cnt==num:
            return string
    else:
        for str in letter:
            if str not in string:
                answer = dfs(string+str,num,letter)
                if answer:
                    return answer
        return None



while True:
    cnt=0
    input_data=input().rstrip().split()

    if len(input_data)!=2:
        break

    a,b=input_data
    b=int(b)

    result=dfs("",b,a)

    if result==None:
        print(a,b,'=','No permutation')
    else:
        print(a,b,'=',result)

 

 

문제 링크

---

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

9742번: 순열