코딩테스트/Python
[Leetcode] 77. Combinations
swwho
2022. 12. 2. 23:58
728x90
반응형
🔗 Problem Link
Combinations - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
❔Thinking
- 1부터 n까지의 숫자들 가운데 k개를 뽑아 조합한 결과를 반환한다.
💻Solution
1. 조합을 활용한 풀이
from itertools import combinations
def combine(self, n: int, k: int):
n_list = [i for i in range(1,n+1)]
return list(combinations(n_list, k))
2. DFS을 활용한 풀이
def combine(self, n: int, k: int):
nums = [i for i in range(1, n+1)]
result = []
stack = [[0, nums, []]]
while stack:
length, integers, ans = stack.pop()
if length == k:
result.append(ans)
else:
for i in range(len(integers)):
stack.append([length+1, integers[i+1:], ans+[integers[i]]])
return result
🗝️keypoint
- DFS를 활용할 때, [1,2] 와 [2,1]를 하나로 합치기 위한 sort나 set()은 시간초과가 발생한다.