leetcode 230(트리), 22(구현), 17(dfs), 136(xor)

230번. https://leetcode.com/problems/kth-smallest-element-in-a-bst/submissions/

pre, in, post중 아무거나 순회한 다음에 원소들을 정렬후 k번째 작은 값을 리턴한다.

class Solution(object):
    def kthSmallest(self, root, k):
        stack = [root]
        tree = []
        while stack:
            node = stack.pop()
            tree.append(node.val)
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
        return sorted(tree)[k-1]

22번. https://leetcode.com/problems/generate-parentheses/

유효한 괄호 집단을 생성하는 구현 문제이다.

class Solution(object):
    def generateParenthesis(self, n):
        res = []
        def combine_paren(s):
            x, l, r, n = s
            if l < r or l > n or r > n:  # l과 r은 n보다 크면 당연히 안되고, l이 여는 괄호인데 닫는 괄호인 r보다 많도록 설정함. 계속 열다가 l이 n보다 커지면 끝남.
                return
            if l == r == n:
                res.append(x)
            combine_paren([x+'(', l+1, r, n])  # 열린 괄호를 추가해줄때 left +1, 닫힌 괄호는 right + 1
            combine_paren([x+')', l, r+1, n])
        combine_paren(["", 0, 0, n])  # 순서대로 만들어진 괄호, left, right, n
        return res

17번. https://leetcode.com/problems/letter-combinations-of-a-phone-number/

번호를 눌렀을시 나올수 있는 알파벳의 조합을 구하여라.

class Solution(object):
    def letterCombinations(self, digits):
        if not digits:
            return []
        digit_dict = {'2':'abc', '3':'def', '4': 'ghi', '5': 'jkl',
                     '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
        digits = map(lambda x: list(digit_dict[x]), digits)
        ret = []
        def dfs(s, digits):
            if not digits:
                ret.append(s)
                return
            for digit in digits[0]:
                dfs(s+digit, digits[1:])
        
        for digit in digits[0]:
            dfs(digit, digits[1:])
        return ret

136번. https://leetcode.com/problems/single-number/

문제를 푸는 것에만 목적을 두면 매우 기본적인 문제이지만, 문제 끝에 추가적인 메모리를 사용하지 않고 할수 있겠냐에 포인트를 맞추자. 모든 숫자가 두번씩 나오며, 한개만 나오는 숫자를 찾는건데,

똑같은 수를 두번 xor하면 0이 되는 성질을 이용한다.

class Solution(object):
    def singleNumber(self, nums):
        r = 0
        for n in nums:
            r ^= n
        return r