[leet22] DFS 인자를 할당된 객체가 아닌 직접 지정해줘야 하는 경우
leetcode 22 Generate Parentheses
DFS에서의 변수 고정
나는 보통 DFS를 돌 때 아래와 같은 방식을 사용한다.
1. 체크할 변수에 root를 반영
2. root에서 다음 갈 수 있는 자리(togo) 선정
3. for loc in togo: 에 대해서 dfs 실행
def helper(path, root, cum):
nonlocal ans, n
if len(path)==n:
ans.append(path)
return
path.append(root)
cum += root
if cum == 0: togo = [1]
if cum == n: togo = [-1]
else: togo[-1, 1]
for loc in togo:
dfs_helper(path, loc, cum)
하지만 이렇게 되면 처음 리프로 다녀와서 두번째 리프를 찾아 나설 때, path가 이미 가득 차 있게 된다. 그렇다고 return 전에 path를 초기화하자니 다음 리프로의 탐색이 path=None 상태에서 다시 시작하는 것도 아니기 때문에 이렇게도 불가능하다.
이 문제에서는 이를 방지하기 위해 변수에 할당하지 않고 직접 재귀함수에 값을 넣어주었다. 한번 리프에 다녀오더라도 고정된 값에서부터 출발하기 때문에 원하는 탐색을 진행할 수 있게 된다.
if cum == 0:
dfs_helper(str1+'(', cum+1)
elif cum == n:
dfs_helper(str1+')', cum-1)
else:
dfs_helper(str1+'(', cum+1)
dfs_helper(str1+')', cum-1)
Question
n쌍의 괄호를 사용해서 유효한 모든 괄호문자 만들기
Solution
PSEUDO 1
- 맨 앞, 맨 뒤에 ( ) 을 각각 넣고 가운데 2n-2개 자리 중 n-1개를 뽑는 combinations 수행, '('가 들어갈 index를 구하는 작업
- pool (가능한 모든 샘플)
- pool의 모든 경우에 대해 isValid
Solution 1도 시간 제한 내에 통과하였으나 포스팅 길이가 길어지니 풀 코드는 아래 github에서 참고
PSEUDO 2
- DFS를 돌리는데, path나 cum에 값을 할당해주면 돌면서 계속 바뀌기 때문에 직접 함수에 집어넣는 형태로
path += ')', cum -= 1처럼.
def sol_2(n):
ans = list()
def dfs_helper(str1, cum):
nonlocal ans, n
if len(str1) == n*2:
if cum == 0:
ans.append(str1)
return
if cum == 0:
dfs_helper(str1+'(', cum+1)
elif cum == n:
dfs_helper(str1+')', cum-1)
else:
dfs_helper(str1+'(', cum+1)
dfs_helper(str1+')', cum-1)
dfs_helper(str(), 0)
return ans
Author And Source
이 문제에 관하여([leet22] DFS 인자를 할당된 객체가 아닌 직접 지정해줘야 하는 경우), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jonas-jun/leet22-DFS-parentheses저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)