[백준 문제] P10974 모든 순열(파이썬)

핵심 : 다음 순열을 만드는 함수 만들고 갱신하면서 print

# 1. 다음 순열을 만드는 def
def next_permutation(a):
    n = len(a) - 1
    i = n
    while i > 0 and a[i-1] >= a[i]:
        i -= 1
    if i == 0: # 마지막 순열
        return False
    j = n
    while a[i-1] >= a[j]: # 오른쪽에 있으면서 a[i-1]보다 큰 수
        j -= 1
    a[i-1], a[j] = a[j], a[i-1] # SWAP
    j = n
    while i < j:
        a[i], a[j] = a[j], a[i] # a[i]부터 순열 뒤집기
        i += 1
        j -= 1
    return True

# 2. n을 입력하고 그 n에 해당하는 초기값 설정
n = int(input())
a=[]
for i in range(1, n+1) :
    a.append(i)

# 3. 초기값과 다음 값들을 출력하고 False가 나오면 끝나게끔 설정
for i in a:
    print(i, end=' ')
print()
while next_permutation(a) is True :
    for i in a:
        print(i, end=' ')
    print()

참고 사이트

진짜 깔끔하게 풀으셨네.. ㄷㄷ

def next_permutation(a):
    n = len(a) - 1
    i = n
    while i > 0 and a[i-1] >= a[i]:
        i -= 1
    if i == 0:
        return False
    j = n
    while a[i-1] >= a[j]:
        j -= 1
    a[i-1], a[j] = a[j], a[i-1]
    j = n
    while i < j:
        a[i], a[j] = a[j], a[i]
        i += 1
        j -= 1
    return True

a = [i+1 for i in range(int(input()))] # 이부분 따라해봐야겠다.
while True:
    print(' '.join(map(str, a))) 
    if next_permutation(a) is False:
        break

[백준 문제] P10974 모든 순열(파이썬)

Share this post