Leetcode 47. Permutations II - Python

Leetcode 47 문제 보기

 

문제 이해하기

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

이 때 nums의 원소 중에는 중복된 값이 존재 가능하다.

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

 

아이디어 구상

본 문제는 <Leetcode 46. Permutations>와 유사하나 주어진 list에 중복된 값이 존재할 수 있다는 차이가 있다.

 

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

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

방법은 다음과 같이 가능한 순열들을 구한 후, set을 취해 중복된 값들을 제거한다.

성능도 제법 준수하다.

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

 

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

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

<Leetcode 46. Permutations>에서는 주어진 list인 nums에 대하여 Decision Tree를 그려보았다.

그러나 본 문제에서는 약간의 트릭이 추가되면 보다 수월하게 문제를 해결 가능하다.

바로 Map을 활용하는 것이다.

단순한 list가 아닌 (key, value) = (원소값, 원소 개수) 쌍을 이용하면, 사용된 값에 해당하는 개수를 줄여나감으로 중복된 순열을 배제하며 결과를 구할 수 있다.

By Mesotes

 

풀이

정답을 담을 리스트, 가능한 순열을 담을 리스트, nums의 (원소값, 원소 개수) 쌍의 Counter 초기화한다.

이 때 Counter는 다음과 같이 구할 수 있다.

counter = {n:0 for n in nums}
for n in nums:
    counter[n] += 1

물론 파이썬에는 이를 수월하게 구할 수 있게 하는 모듈이 있다.

collections의 Counter를 활용하자.

res = []
possible = []
nums_map = collections.Counter(nums)

 

base case는 다음과 같다.

생성한 순열의 길이가 nums의 길이와 같다면 res에 해당 순열을 append하고 종료한다.

 

순열을 그대로 append하지 않고 copy를 하는 이유는 앞선 포스팅에서 설명한 바 있다.

Leetcode 46. Permutations 풀이-base case 참조

if len(possible) == len(nums):
    res.append(possible[:])
    return

 

재귀 부분은 다음과 같다.

만약 사용하지 않은 nums의 원소(nums_map의 value > 0)가 있다면 nums의 원소(nums_map의 key값)를 순열(possible)에 추가한다. 계속해서 dfs()를 돌리고 이후 base case 만족 시 return을 통해 가능한 순열을 res에 append한다. 마지막으로 감소시켰던 원소의 개수를 다시 늘리고, possible을 초기화함으로써 다음 순열을 찾도록 코드를 작성했다.

for i in nums_map:
    if nums_map[i] > 0:
        possible.append(i)
        nums_map[i] -= 1
                    
        dfs()
                    
        nums_map[i] += 1
        possible.pop()

 

전체 코드는 다음과 같다.

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        res = []
        possible = []
        # 1 <= nums.length <= 8, -10 <= nums[i] <= 10
        nums_map = collections.Counter(nums)
        
        def dfs():
            # base case
            if len(possible) == len(nums):
                res.append(possible[:])
                return
            
            for i in nums_map:
                if nums_map[i] > 0:
                    possible.append(i)
                    nums_map[i] -= 1
                    
                    dfs()
                    
                    nums_map[i] += 1
                    possible.pop()
                    
        dfs()
        return res

 

---

Leetcode 47. Permutations II

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

​

 

 

 

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

 

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

 

 

 

 

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

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