[알고리즘 문제] 순열 구하기 (Python / 파이썬)

문제

서로 다른 n개의 원소들 중에서 r개만을 뽑아 일렬로 나열하는 것을 순열이라 한다. 예를 들어, 3개의 원소 a, b, c 중에서 2개만을 뽑아 나열하면 ab, ac, ba, bc, ca, cb 의 6가지 경우가 있다. n과 r이 주어질 때, n개의 소문자 중에서 r개만을 뽑아 나열하는 모든 경우를 출력하는 프로그램을 작성하시오. 단, a부터 시작하여 연속으로 n개의 알파벳을 갖고 있다고 하자. 

입력

첫 번째 줄에 n과 r이 주어진다. ( 1 ≤ n ≤ 10, 0 ≤ r ≤ min(n, 7) ) 

출력

각 줄에 n개의 소문자 중에서 r개만을 뽑아 나열하는 경우를 사전순으로 나열한 결과를 출력한다.

---

문제 풀이

n개의 소문자 중에서 r개만을 뽑는데 이때 중복이 없어야 합니다. 

따라서 check 배열을 따로 만들어 중복을 피하도록 해주었습니다.

 

for문을 이용하여 0부터 n-1까지의 원소들 중 만약 아직 넣지 않은 원소라면

x 인덱스에 넣어주고 원소를 넣어줬다고 표시해주었습니다.

다시 재귀함수를 이용하여 x+1을 넘겨주어 실행해줍니다. 

그렇다면 0부터 n-1까지의 원소들 중 만약 아직 넣지 않은 원소라면 

x+1 인덱스에 넣어주고 원소를 넣어줬다고 표시해줍니다.

 

이때, 만약 x 값이 r보다 같거나 커진다면 r개를 뽑았다는 뜻이므로 

해당 array를 출력하도록 해주었습니다.

출력해줄 때는 소문자로 출력해야 하므로 chr() 함수를 이용해주었습니다.

 

여기서 주의해야할 점은 r개의 원소를 뽑을 때마다

check 배열과 array를 초기화 해주어야 한다는 것입니다. 

---

My Code 

# 순열 구하기 함수
def permutation(x):
    if x >= r: # r개를 뽑았다면
        for i in range(r):
            print(chr(array[i] + 97), end = '') # 출력
        print()
    else:
        for i in range(n):     # 0~n-1 원소 중
            if check[i] == 0:  # 아직 사용하지 않았다면
                array[x] = i   # 해당 인덱스에 삽입
                check[i] = 1   # 사용했다고 표시
                permutation(x + 1) # 다음 인덱스 넘겨줌
                array[x] = 0   # array 원상복구
                check[i] = 0   # check 원상복구

n, r = map(int,input().split())

array = [0] * 100 # 뽑은 원소를 저장할 배열
check = [0] * 100 # 사용한 원소인지 확인할 배열

permutation(0)