백준 15650번_N과 M (2) [python/파이썬]

 

# 직접 작성한 코드

N, M = map(int, input().split())
 
check_list = [False]*N
num_list = [i for i in range(1,N+1)]
 
output = []
result = []
 
def permutation(count):
    if count == M:
        if [*check_list] not in result:
            result.append([*check_list])
        return
 
    for i in range(N):
        if check_list[i] == True:
            continue
 
        output.append(num_list[i])
        check_list[i] = True
        permutation(count+1)
        output.pop()
        check_list[i] = False
    return result
 
result = permutation(0)
for i in range(len(result)):
    for j in range(len(result[i])):
        if result[i][j] == True:
            print(j+1, end=' ')
    else:
        print()

 N과 M (1)의 코드에서 True, False의 값을 저장하는 result 배열을 추가하여 중복요소를 제거한다. 하지만 이럴 경우 permutation 함수가 진행되고 난 뒤에도 이중 포문을 수행해야하기 때문에 효율적이지 않다. 

 

 

# 구글링 중 발견한 '대학원생이 쉽게 설명해보기' 블로그에서 완성도가 높은 코드가 있어 첨부해보았다.

출처: '대학원생이 쉽게 설명해보기' 블로그