항해99 2주차 - 순열

Today I learned
2022/01/20

회고록

1/20

항해 99, 알고리즘 1주차

교재 : 파이썬 알고리즘 인터뷰

12장 그래프

1. 이론

https://velog.io/@jsw4215/%ED%95%AD%ED%95%B499-2%EC%A3%BC%EC%B0%A8-%EA%B7%B8%EB%9E%98%ED%94%84DFSBFS-%EC%9D%B4%EB%A1%A0-%EC%A0%95%EB%A6%AC

2. 문제

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Example 1:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Example 2:

Input: nums = [0,1]
Output: [[0,1],[1,0]]
Example 3:

Input: nums = [1]
Output: [[1]]

Constraints:

1 <= nums.length <= 6
-10 <= nums[i] <= 10
All the integers of nums are unique.

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

3. MySol

• Recursive DFS

def solution(nums):
    results = []
    prev_elements = []

    def dfs(elements):
        print('=======================================================')
        if len(elements) == 0:
            results.append(prev_elements[:])
            print(f'results : {results} dfs 종료')

        for e in elements:
            next_elements = elements[:]
            print(f'next_elements : {next_elements}, e : {e}')
            next_elements.remove(e)
            print(f'next_elements.remove(e) : {next_elements}')

            prev_elements.append(e)
            print(f'elements : {elements}, prev_elements : {prev_elements}, next_elements : {next_elements}, dfs 호출')
            dfs(next_elements)
            print(f'before prev_elements.pop() : {prev_elements}')
            prev_elements.pop()
            print(f'after prev_elements.pop() : {prev_elements}')

        print('+++++++++++++++++++++++++++++++++++++++++++++++++++++++ end for : result : ' + str(results))

    dfs(nums)
    return results


if __name__ == '__main__':

    inputNum = [1,2,3]

    result = solution(inputNum)

    print('result : ' + str(result))

4. 배운 점

• 해당 문제는 이해하게 되면 DFS및 재귀함수에 대해 이해하는데 굉장히 큰 도움이 되는 문제이다.

5. 총평

재귀, DFS 훈련