[백준] 10974번
[백준] 10974번 모든 순열
📌순열이란?
서로 다른 n개의 원소에서 r개를 중복없이 순서를 고려하여 선택하거나 나열하는 것
nPr = ${n! \over (n-r)!}$
[문제]
N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오.
[입력]
첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다.
[출력]
첫째 줄부터 N!개의 줄에 걸쳐서 모든 순열을 사전순으로 출력한다.
n = int(input())
temp = []
def per():
if len(temp) == n:
print(*temp)
return
for i in range(1, n + 1):
if i not in temp:
temp.append(i)
per()
temp.pop()
per()
우선 n을 입력 받고 생성한 순열을 담아 출력할 리스트를 생성해줍니다.
그리고 함수를 생성합니다. 함수는 조건문을 통해서 리스트의 길이가 n과 같아지면 출력하도록합니다.
이제 반복문을 통해서 순열을 생성해줍니다. 범위는 1
부터 n+1
까지 반복하는데 , n이 3일 때를 예시로 들어 설명하겠습니다.
만약 리스트에 i가 없으면 리스트에 i를 담아줍니다.
n = 3
1)
i=1일때,
만약 리스트에 1이 없으면 리스트에 1을 담아줍니다.
➡️ i=1, temp=[1]
dfs()를 호출합니다.
1)-1
i = 1인 경우는 이미 리스트안에 존재합니다.
i=2
i=2는 리스트안에 존재하지 않습니다. 그래서 리스트에 담아주고 dfs()를 호출합니다.
1)-2
i=1, i=2인경우는 리스트에 존재해서 패스하고
i=3
일 때는 없으니 리스트에 담아주고 dfs()를 호출합니다.여기서 temp=[1, 2, 3]이고
if len(temp) == n:
을 만족하기 때문에 리스트 값 [1, 2, 3]을 출력하고 return 합니다.temp.pop()을 실행합니다. ➡️ temp = [1, 2]
여기서 호출된 dfs()는 i=3까지 반복해서 이 dfs()를 호출한 1)-1로 돌아갑니다.
i=2
일때 dfs()로 돌아와서 temp.pop()을 합니다.➡️ temp=[1]
다시 반복문을 진행해서
i=3
인 경우를 보니 리스트에 3은 존재하지 않기 때문에 리스트에 담아줍니다.
temp=[1, 3]
그리고 dfs()를 호출합니다.
i=1은 있으니 넘어가고 i=2가 리스트안에 넣어줍니다.
[1, 3, 2]를 출력합니다.
다시 리턴되어 temp.pop()가 되어 [1, 3]이되고
i=3
은 리스트에 있으니 반복문이 종료되어 이전 호출로 갑니다.이러한 과정을 반복해서 모든 수열을 얻을 수 있습니다.
댓글남기기