Leetcode 46. Permutations - Python (cf. 백준 10974)

Leetcode 46 문제 보기

 

문제 이해하기

주어진 숫자 리스트 nums의 원소들을 이용하여 생성가능한 순열을 출력하라.

이 때 가능한 순열들의 출력은 어떤 순서로 해도 상관없다.

 

아이디어 구상

반복문을 이용한 iterative한 방법, 재귀를 통한 recursive한 방법 등 다양한 방법으로 문제를 풀 수 있다.

그 중 온라인 코딩 테스트에서는 순열을 생성하는 라이브러리를 활용해서 쉽게 구하도록 하자.

파이썬의 경우, itertools를 활용하면 된다.

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        return list(itertools.permutations(nums))

 

하지만 만약 화이트보드 인터뷰라면?

Decision Tree를 그리며 생각해보자.

Decision Tree를 그리는 방법도 여러가지가 있겠으나, 우선 크게 2가지가 떠오른다.

빈 list에서부터 출발해 원소를 하나씩 채워가는 방법과 전체 nums에서 원소를 하나씩 제거하는 방법이다.

 

여기서는 후자를 활용해 문제를 풀어보자.

nums = [1, 2, 3] 일 경우의 test case를 살펴보자.

By Mesotes

맨 처음 nums에서 첫 번째 원소를 pop하면 [2, 3]이 된다.

즉, [1, 2, 3]일 때의 permute을 구해야하는 문제가 [2, 3]일 때의 permute를 구해야하는 sub problem으로 문제가 작아졌다. 마찬가지로 [2, 3]에서 첫 원소를 제거하면 permute([3])으로 문제가 작아진다.

 

이렇게 분해를 진행하다가 원소가 하나 존재할 경우, 즉, base case를 만족하게 되면 방금 전 pop했던 원소를 뒤에 추가해주면서 다시 거꾸로 올라가며 순열을 만든다.

풀이

정답을 담을 리스트를 선언한다.

res = []

 

base case는 다음과 같다.

만약 leaf node에 도달했다면, 즉, 리스트의 원소가 하나 존재할 경우 이를 return한다.

여기서 주의할 점은, nums를 그대로 return해서는 안된다는 것이다.

 

파이썬의 경우, 모든 것이 객체다. 숫자, 문자는 물론 list 또한 마찬가지다.

객체를 그대로 리턴할 경우, 같은 주소를 참조하는 동일한 값이 리턴된다.

때문에 해당 객체의 값이 바뀌면 리턴된 값 또한 영향을 받는다.

따라서 값 자체를 복사하려면 copy()를 해야한다.

이 때 슬라이싱을 이용하면 빠르게 복사된다.

cf) 2차원 이상의 복잡한 list의 경우, [복사된 list] = copy.deepcopy([복사할 list]) 를 통해 copy가능하다.

if len(nums) == 1:
    return [nums[:]]

 

재귀 부분은 다음과 같다.

아이디어 구상에서 살펴봤듯이, 첫 원소를 pop()하고 재귀를 통해 문제를 작게 분해한다.

이후 pop()했던 원소를 뒤에 추가하면서 다시 거꾸로 올라가며 순열을 result에 추가해나간다.

for i in range(len(nums)):
    n = nums.pop(0)
    perms = self.permute(nums)

    for perm in perms:
        perm.append(n)
    res.extend(perms)
    nums.append(n)

 

전체 코드는 다음과 같다.

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []

        # base case
        if len(nums) == 1:
            return [nums[:]]

        for i in range(len(nums)):
            n = nums.pop(0)
            perms = self.permute(nums)

            for perm in perms:
                perm.append(n)
            res.extend(perms)
            nums.append(n)
        return res

 

---

백준 10974번 문제는 위와 같은 문제다.

백준 10974 문제 보기

 

문제 이해하기

input 값의 형태에 차이가 있고 output은 사전순으로 출력되어야할 뿐, 문제는 동일하다.

 

아이디어 구상

이번에는 빈 list에서부터 출발해 원소를 하나씩 채워가는 Decision Tree를 그리며 문제를 해결해보자.

By Mesotes

이 경우, Tree의 leaf node들이 바로 가능한 순열들이다.

풀이

dfs()의 base case는 다음과 같다.

만약 leaf node에 도달했다면, 즉, depth == len(nums)일 경우 res에 가능한 순열을 append한다.

if depth == len(nums):
    res.append(v)
    return

 

전체 코드

n = int(input()) # 1 ≤ N ≤ 8
nums = [i for i in range(1, n + 1)]

res = []


def dfs(depth, v):
    # base case
    if depth == len(nums):
        res.append(v)
        return

    for num in nums:
        tmp = v[:]
        if num not in tmp:
            tmp.append(num)
            dfs(depth + 1, tmp)

dfs(0, [])
for result in res:
    print(*result)

 

---

Leetcode 46. Permutations

https://leetcode.com/problems/permutations/​

 

백준 10974. 모든 순열 (실버 3)

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

 

 

 

 

-문제해결흐름을 간단히 정리한 주관적 포스팅-

 

-부족한 설명이 있다면 부디 조언 부탁드립니다-

 

 

 

 

이 포스팅은 쿠팡 파트너스 활동의 일환으로,

이에 따른 일정액의 수수료를 제공받습니다