[Silver III] 순열 - 9742

문제 링크

성능 요약

메모리: 113496 KB, 시간: 1216 ms

분류

브루트포스 알고리즘, 백트래킹

제출 일자

2026년 3월 9일 19:22:15

문제 설명

집합의 순열이란 집합의 서로 다른 원소를 모두 사용해 만들 수 있는 순서이다. 예를 들어, {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

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

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 문자열은 서로 다른 숫자와 알파벳으로 이루어져 있으며, 길이는 최대 10이다. 또한, 사전순 순서대로 주어진다. 문자열 다음에는 찾아야 하는 위치가 주어지며, 이 값은 3,628,800보다 작거나 같은 자연수이다.

출력

각각의 테스트 케이스마다, 입력으로 주어진 위치에 해당하는 순열을 공백없이 출력한다. 만약, 해당하는 순열이 없는 경우에는 "No permutation"을 출력한다.

---

💡 해결 방법

💻 코드

# https://www.acmicpc.net/problem/9742
 
while 1:
    try:
        s, x = (input().split())
        s = sorted(list(str(s)))
        # print(s, x)
        
        count = 0
        ans = []
        n = len(s)
        visited = [-1 for i in range(n)]
        flag = 0
        
        def back(buck, now):
            global count
            global flag
            if len(buck) == n:
                count += 1
                if count == int(x):
                    print(f"{''.join(s)} {x} = ", end ='')
                    print("".join(buck))
                    flag = 1
                return
            if now == n:
                return
            
            for i in range(n):
                if visited[i] == -1:
                    visited[i] = 1
                    back(buck + [s[i]], now + 1)
                    visited[i] = -1
 
 
        back([], 0)
        
        if flag == 0:
            print(f"{''.join(s)} {x} = ", end ='')
            print("No permutation")
    except:
        break