You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
itertools 모듈을 사용하지 않고 풀이1 보다 실행 시간이 더 짧은 코드를 작성해봤습니다.
리트코드에서 풀이1은 412ms, 제가 작성한 코드는 92ms가 소요됩니다.
class Solution:
def combine(self, n: int, k: int) -> list[list[int]]:
# depth 는 재귀적으로 불린 횟수 번호를 의미합니다.
# 예를들어 dfs 를 처음 부르면 depth 는 1이고, 더 이상 재귀를 하지 않으면 원소가 1개인 결과 생성
# depth 가 2이고, 더 이상 재귀를 부르지 않으면 원소가 2개인 결과 생성
# depth 와 필요한 원소의 갯수인 k 를 비교해서 재귀 호출에 제한을 만들었습니다.
def dfs(num_range: int, depth: int):
if depth > k:
return
res = []
# k 개의 조합을 만들어야 하는데 처음 숫자값이 k 보다 작을 경우, k개의 조합이 생성될 수 없음
# ex) k=4, 시작 숫자가 3 일 경우, (3, 2, 1) ... 숫자가 부족함
# 재귀적으로 호출되는 점을 고려해서 이것을 k-depth 로 구현함
for num in range(num_range, k-depth, -1):
sub_res = dfs(num-1, depth+1)
if sub_res:
for sub_list in sub_res:
sub_list.append(num)
res.append(sub_list)
else:
res.append([num])
return res
return dfs(n, 1)
ans = Solution.combine(Solution(), 4, 2)
print(ans)
The text was updated successfully, but these errors were encountered:
itertools 모듈을 사용하지 않고 풀이1 보다 실행 시간이 더 짧은 코드를 작성해봤습니다.
리트코드에서 풀이1은 412ms, 제가 작성한 코드는 92ms가 소요됩니다.
The text was updated successfully, but these errors were encountered: