[Python] 백준 15654: N과 M(5) (함수형 프로그래밍에서 중시하는 Immutable)

문제 링크

15654번: N과 M(5)

문제 요약

N개의 서로 다른 정수가 주어진다. 이 때 서로 다른 정수로 길이가 M인 수열을 사전 순서대로 출력하세요.

풀이 설명

이 문제가 조건 아래에서 가능한 모든 경우를 탐색하는 백트래킹 알고리즘 유형인 것에 맞게, 모든 경우의 수열을 재귀적으로 탐색하여 출력하였다. (DFS)

더욱이 사전 순서대로 출력하는 것이어서 DFS 방식으로 경우를 탐색하는 것이 적절했다.

N, M=map(int, input().split())
nums=list(map(int, input().split()))
nums=sorted(nums)

def dfs(nums_print, nums_left):
    if len(nums_print)==M:
        for i in range(M):
            print(nums_print[i], end=" ")
        print()
        return
    
    elif len(nums_print)<M:
        for i in range(len(nums_left)):
            dfs(nums_print+[nums_left[i]], nums_left[:i]+nums_left[i+1:])

for i in range(N):
    dfs([nums[i]], nums[:i]+nums[i+1:])

 

처음 문제를 풀며 실수했던 부분은 remove 함수의 잘못된 사용이었다.

dfs 함수를 보면, 전체 N개의 숫자 중에서 출력할 리스트로 저장되는 nums_print와 남은 숫자들인 nums_left로 입력값을 주는데, 기존에는 아래와 같은 방식으로 함수를 실행했다.

for num in nums:
	dfs([num], nums.remove(num))

 

remove는 해당 num 값을 삭제한 list를 반환하는 것이 아니라 해당 list에서 직접 num 값을 삭제하기 때문에 의도하지 않은 nums 값의 변경이 계속 발생하면서, 원하지 않은 결과값이 출력되고 있었다.

 

이는 list slicing으로 함수의 인자를 입력함으로써 해결하였다.

더불어 이처럼 프로그램을 함수로 쪼개어 구현하는 코드 작성 방식을 함수형 프로그래밍이라고 하는데, 이 때 데이터의 불변성(Immutable)이 무엇이고 어떻게 지킬 수 있는지 이해할 수 있었다.

※ Python은 객체지향 프로그래밍 언어라 불리지만, 함수형 프로그래밍, 객체지향 프로그래밍, 절차형 프로그래밍이 모두 수월하게 가능한 다중 패러다임 언어이다.

함수형 프로그래밍을 할 때, Immutable을 지키면 더욱 코드 짜기가 편해진다.