[백준] 10974 모든 순열 파이썬 python

문제링크

https://www.acmicpc.net/problem/10974

10974번: 모든 순열

 

코드

방법1

import sys
input = sys.stdin.readline
 
n = int(input())
a = list(range(1,n+1))
 
def bf(arr,cur):
    if arr:
        for i in range(n-len(cur)):
            temp = list(cur)
            temp.append(arr[i])
            new_arr = arr[:i]+arr[i+1:]
           bf(new_arr,temp)
    else:
        print(*cur)
bf(a,[])
 
 

방법2

import sys
input = sys.stdin.readline
 
def next_permutation(cur):
    for i in range(n-1,0,-1):
        if cur[i-1]<cur[i]:
            target = i-1
            break
    else:
        return -1
    for i in range(n-1,0,-1):
        if cur[target]<cur[i]:
            cur[target],cur[i] = cur[i],cur[target]
            break
    nxt = cur[:target+1] + sorted(cur[target+1:])
    return nxt
 
n = int(input())
cur = list(range(1,n+1))
 
tot =[]
tot.append(cur)
 
while True:
    cur = list(cur)
    nxt = next_permutation(cur)
 
    if nxt!=-1:
        tot.append(nxt)
        cur = list(nxt)
    else: break
 
for cur in tot:
    print(*cur)

 

POINT

방법1

bf(arr,cur) : arr은 후보군 배열, cur 현재까지 완성된 배열

후보군 arr에서 arr[i] 하나 가져와 cur에 붙여넣고(temp = cur+arr[i]) , 방금 가져온 arr[i]는 후보군에서 뺀 새로운 후보군 new_arr을 만든다. bf(new_arr, temp)을 후보군이 다 떨어질때까지 반복 호출한다.

 

방법2

다음 순열 next_permutation 구현 코드를 그대로 사용하여 구현한다.

https://rrojin.tistory.com/46

[백준] 10972 다음 순열 파이썬 python

---

* 얕은 복사 vs 눈속임 얕은 복사

얕은 복사 : b = a    ----> a변경 사항이 b에도 반영되기 때문에 '='를 함부로 사용하면 안된다. 

눈속임 얕은 복사 : c = list(a) / d=a.copy() / e = a[:]               ----> a변경 사항 반영 X       

a = [1,2,3]
b = a
c = list(a)
d = a.copy()
e= a[:]
 
a.append(4)
 
print(b) #[1,2,3,4]
print(c) #[1,2,3]
print(d) #[1,2,3]
print(e) #[1,2,3]
 
print(hex(id(a))) #0x16bf588a500
print(hex(id(b))) #0x16bf588a500
print(hex(id(c))) #0x16bf58de980 --> a,b와 다름