[🥈3 / 백준 10974 / 파이썬] 모든 순열

 

10974번: 모든 순열

 

문제

N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다. 

출력

첫째 줄부터 N!개의 줄에 걸쳐서 모든 순열을 사전순으로 출력한다.

 

예제 입력  3

예제 출력  1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1

 

풀이

 

브루트 포스 알고리즘을 이용해 만들 수 있는 모든 순열을 사전순으로 출력하는 문제이다.

 

재귀를 이용하였으며, 재귀를 할 때 사용한 숫자를 리스트에서 제거하고 넘기는 방식으로 코드를 작성했다.

 

n = int(input())
s = [str(i+1) for i in range(n)]

def bf(arr,r):
    if arr:
        for i in range(n-len(r)):
            temp = list(r)
            temp.append(arr[i])
            new_arr = arr[:i] + arr[i+1:]
            bf(new_arr,temp)
    else:
        print(*r)

bf(s,[])