[백준 | 실버5] 9742: 순열(백트랙킹, 중복x순열)

https://www.acmicpc.net/problem/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

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

입력

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

출력

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

예제 입력 1 복사

235 4
bein 20
123456 700
mnpqr 130
tuvwxyz 4000

예제 출력 1 복사

235 4 = 352
bein 20 = nbie
123456 700 = 651342
mnpqr 130 = No permutation
tuvwxyz 4000 = ywuxvzt

문제풀이

주어진 문자열에서 문자열의 길이만큼 m개 뽑아서 중복 없는 수열을 만든다

만든 수열결과에서 입력받은 num 번째의 결과물을 반환한다.

 

문제해결

m개 뽑은 수열 결과를 모두 perm_list에 다 저장해두고, 다 만든 후에 찾어야 하는 순서(num)으로 접근하여 답을 도출했으나, 메모리가 터져버림

def DFS(L) :
    if L == m :
        #print(" ".join(map(str, result)))
        perm_list.append(result[:])
        return
    else :
        for i in range(m) :
            if check[i] == False :
                check[i] = True
                result.append(s_list[i])
                DFS(L+1)
                check[i] = False
                result.pop()

while True :
    try : 
        string, num = input().split()
    except :
        break

    s_list = list(map(str, string))         #입력받은 string의 list화
    m = len(s_list)                         #m개 뽑음
    result = []                             #매번 순열로 만든 결과 저장
    perm_list = []                          #m개의 완성된 순열 저장
    check = [False] * m                     #순열은 중복방문 미허용으로 체크 필요
    
    DFS(0)
    if len(perm_list) >= int(num) :
        print(f'{string} {num} = {"".join(perm_list[int(num)-1])}')
    else :
        print(f'{string} {num} = No permutation')

 

그래서 만들어지는 수열이 만들어 질때 결과의 카운트만 체크하고 찾아야 하는 num과 count가 같아 질때만

값을 문자열로 저장과 flag = True로 변경

flag가 True일 경우에만 정답 출력

flag가 false인 경우 수열을 정답까지 만들어낼수 없어 "No permutation" 결과 출력

def DFS(L) :
    global count
    global flag
    global answer
    if L == m :
        count += 1
        if count == int(num) :
            answer = "".join(map(str, result))
            flag = True
        return
    else :
        for i in range(m) :
            if check[i] == False :
                check[i] = True
                result.append(s_list[i])
                DFS(L+1)
                check[i] = False
                result.pop()

while True :
    try : 
        string, num = input().split()
    except :
        break

    s_list = list(map(str, string))         #입력받은 string의 list화
    m = len(s_list)                         #m개 뽑음
    result = []                             #매번 순열로 만든 결과 저장
    check = [False] * m                     #순열은 중복방문 미허용으로 체크 필요
    count = 0
    answer = ''
    flag = False
    
    DFS(0)
    if flag is True :
        print(f'{string} {num} = {answer}')
    else :
        print(f'{string} {num} = No permutation')