[TIL_Carrotww] 93 - 23/01/27

유형석·2023년 1월 27일

algorithm python

TIL

목록 보기

108/138

📝Carrotww의 코딩 기록장

🧲 python algorithm interview

🔍 Leetcode 46 Permutations - Medium

itertools를 사용하여 풀면 아주 간단하게 풀 수 있지만 dfs, bfs를 연습하고 있기때문에 해당 방식으로 올려본다.

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

        def dfs(num_list):
        	if len(num_list) == 0:
            	result.append(word[:])
            for num in num_list:
            	next_num_list = num_list[:]
                next_num_list.remove(num)
                word.append(num)
                dfs(next_num_list)
                word.pop()
        dfs(nums)
        return result

🔍Leetcode 77 Combinations - Medium

이 문제 또한 itertools로 풀이하면 한줄풀이가 가능하지만 dfs로 풀었다.

내 풀이

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        result = []

        def dfs(index, word_list):
            if len(word_list) == k:
                result.append(word_list)
                return

            for i in range(index, n+1):
                dfs(i+1, [*word_list, i])

        dfs(1, [])
        return result

word_list를 언팩킹 하여 넘겨주었다.

책 풀이

class Solution:
    def combine(self, n:int, k:int) -> List[List[int]]:
        result = []

        def dfs(num_list, start, k):
            if k == 0:
                result.append(num_list[:])
                return

            for i in range(start, n+1):
                num_list.append(i)
                dfs(num_list, i+1, k-1)
                num_list.pop()
        dfs([], 1, k)
        return result

🔍 Leetcode 39 Combination Sum - Medium

내 풀이

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        result = []

        def dfs(num_list):
            if sum(num_list) == target:
                temp = sorted(num_list)
                if temp not in result:
                    result.append(temp)
            elif sum(num_list) > target:
                return
            for i in range(len(candidates)):
                num_list.append(candidates[i])
                dfs(num_list)
                num_list.pop()
        dfs([])
        return result

사실상 permutation 으로 모든 경우의 수를 본 다음 sort까지 하고 list에서 존재하는지까지 찾기 때문에 속도는 최악이다.
난이도가 높은 풀이였다면 절대 안풀렸을 풀이다.

개선한 풀이
index를 주어 앞 부분은 반복하지 않게 구현했다.

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        result = []
        def dfs(csum, index, path):
            if csum < 0:
                return
            elif csum == 0:
                result.append(path[:])
                return
            for i in range(index, len(candidates)):
                path.append(candidates[i])
                dfs(csum - candidates[i], i, path)
                path.pop()
        dfs(target, 0, [])
        return result