반응형
문제
N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다.
출력
첫째 줄부터 N!개의 줄에 걸쳐서 모든 순열을 사전순으로 출력한다.
예제 입력 1
3
예제 출력 1
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
나의 풀이
10972번 다음 순열 문제를 풀었다면 응용하여 풀 수 있다. 1부터 n까지의 리스트를 만들고, 다음 순열을 구하는 함수와 순열을 print해주는 함수를 만들어 k가
-1
이 나올때까지 반복을 해주었다.
코드
# 10974번 모든 수열
# 순열 찾기
def find(bs):
k = -1
# 1. k의 최댓값 구하기
for i in range(len(bs)-1):
if bs[i] < bs[i+1]:
k = i
# 마지막
if k == -1:
return -1
# 2. m의 최댓값 구하기
for j in range(k+1,len(bs)):
if bs[k] < bs[j]:
m = j
# 3. k와 m 바꿔치기
bs[k], bs[m] = bs[m], bs[k]
# 4. k 이후 오름차순으로 정렬
tmp = bs[k+1:]
tmp.sort()
return bs[:k+1] + tmp
# print
def printSeq(s):
for num in s:
print(num, end=' ')
print()
# main
n = int(input())
seq = [x for x in range(1,n+1)]
while True:
printSeq(seq)
seq = find(seq)
if seq == -1:
break
반응형
'Programming > Algorithm' 카테고리의 다른 글
[백준10971번] 외판원 순회 2 / Python3 (0) | 2020.04.15 |
---|---|
[백준10819번] 차이를 최대로 / Python3 (0) | 2020.04.15 |
[백준10973번] 이전 순열 / Python3 (1) | 2020.04.14 |
[백준10972번] 다음 순열 / Python3 (0) | 2020.04.14 |
[백준14500번] 테트로미노 / Python3 (0) | 2020.04.14 |