log 2022-04-17

---

• blog
• sport
  • leet - generate parentheses
• arb

blog

한 달마다 이전 달의 포스트들을 해당 년도 폴더로 옮겨야 겠다.

sport

leet - generate parentheses

한 괄호가 추가 될 때의 경우의 수가 늘어나는 규칙을 세어보기.

1. ()
2. ()(), (()) = 1 + 1
3. 위에서 넣을 수 있는 위치 1, 2, 3, 4, 5 -> (())(), ()()(), ()(()), ((())), (())() = 3 + 2
4. 3 + 4 + 3 + 2 + 3 = 15

1 1+1 3+2 3+4+3+2+3

안쪽에 추가한 경우 다음 경우의 수 증가에는 영향이 없고, 오른쪽에 추가한 경우 +1 증가된다.

각 단계에서 닫을지 더 열지 선택하면 되고, 다 썼으면 다 닫고 추가하면 된다.

그냥 각 스텝에서 (무한반복은 안 나게) 가능한 선택 마음대로 하고, 종료 조건만 잘 체크하면 되는데, right가 여러 개 남아있는 경우를 처리하려고 해서 잘 안풀렸다. 사실 각 단계에서 right를 하나 닫는 케이스만 추가하는 것으로 충분했다.

py solution

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans = []
        def dfs(left, to_close, cur):
            if left < 0 or to_close < 0:
                return
            if left == 0 and to_close == 0:
                ans.append(''.join(cur))
                return
            
            # 1. add (
            if left > 0:
                cur.append('(')
                dfs(left-1, to_close+1, cur)
                cur.pop()
                
            if to_close > 0:
                cur.append(')')
                dfs(left,to_close-1,cur)
                cur.pop()
            return
        
        dfs(n, 0, [])
        return ans

arb

일단 그 인터페이스 두는 부분 완료. 스레드 다 제거하고 asyncio로 바꿀 생각은 못했다.

---