[leetcode] 91, 98, 169, 171

169. Majority Element

https://leetcode.com/problems/majority-element/

My Answer 1: Accepted (Runtime: 160 ms - 84.75% / Memory Usage: 15.4 MB - 96.23%)

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count = collections.Counter(nums)
        
        for k, v in count.items():
            if v > len(nums) // 2:
                return k

Counter 로 n // 2 보다 큰 횟수만큼 나온 key return

My Answer 1: Accepted (Runtime: 156 ms - 93.66% / Memory Usage: 15.5 MB - 82.01%)

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        return sorted(nums)[len(nums)//2]

n // 2 만큼은 보장된거니까 정렬 후 n // 2 번째 값 return
한줄로도 가능~

---

171. Excel Sheet Column Number

https://leetcode.com/problems/excel-sheet-column-number/

My Answer 1: Accepted (Runtime: 28 ms - 89.68% / Memory Usage: 14.1 MB - 90.46%)

class Solution:
    def titleToNumber(self, columnTitle: str) -> int:
        # A -> 65
        ans = 0
        p = 1
        for i in range(len(columnTitle)-1, -1, -1):
            ans += (ord(columnTitle[i]) - 64) * p
            p *= 26
        
        return ans

아스키 코드 이용 => A = 65 니까 64 를 빼줘서 1 로 만들어줌

거꾸로 보면서 숫자 더해주기
자릿수가 늘어날 때마다 26 곱한 값을 더해주면 된다

---

91. Decode Ways

https://leetcode.com/problems/decode-ways/

My Answer 1: Time Limit Exceeded (23 / 269 test cases passed.)

class Solution:
    def numDecodings(self, s: str) -> int:
        if s[0] == "0":
            return 0
        
        lists = list(s)
        if "0" in lists:
            i = 1
            while i < len(lists):
                if lists[i] == "0":
                    if len(lists[i-1]) > 1:
                        return 0
                    lists[i-1] += "0"
                    lists.pop(i)
                else:
                    i += 1
        
        def func(s):
            if s not in self.ans:
                self.ans.append(s)
            if len(s) == 0:
                return
            
            for i in range(len(s)-1):
                c = s[i]+s[i+1]
                if int(c) > 0 and int(c) < 27:
                    func(s[:i]+[c]+s[i+2:])
        
        self.ans = []
        func(lists)
        
        return len(self.ans)

0 으로 시작하는 숫자가 있으면 안되니까 먼저 처리해줌

s 는 list 로 바꿔서 혼자 있는 0 은 앞 숫자뒤에 붙여줌 => 안되면 return 0

그러고 재귀 돌려서 조합 찾아주기
1 ~ 26 까지의 숫자들만 두개씩 하나의 숫자로 합쳐줌

타임리밋일 줄 알았읍니다...

dp 를 써야할 거 같은데 시간이 없어서 못함..^^

Solution 1: Accepted (Runtime: 24 ms - 96.80% / Memory Usage: 14.3 MB - 40.58%)

class Solution:
    def numDecodings(self, s: str) -> int:
        dp = {}
        return self._dp_helper(s, dp)

    def _dp_helper(self, data, dp):
        if not data:
            return 1

        first_call, second_call = 0, 0

        if data in dp:
            return dp[data]

        if 1 <= int(data[:1]) <= 9:
            first_call = self._dp_helper(data[1:], dp)

        if 10 <= int(data[:2]) <= 26:
            second_call = self._dp_helper(data[2:], dp)

        dp[data] = first_call + second_call

        return dp[data]

DP 이용

if 1 <= int(data[:1]) <= 9: => 한자리씩 범위 체크
first_call = self._dp_helper(data[1:], dp)
=> if 문에서 확인한 자리 이후의 값들도 재귀로 한자리씩 범위 체크

if 10 <= int(data[:2]) <= 26: => 두자리씩 범위 체크
second_call = self._dp_helper(data[2:], dp)
=> if 문에서 확인한 자리 이후의 값들도 재귀로 두자리씩 범위 체크

dp 에는 생성 가능한 경우의 수 저장
ex) 12345 => dp = {'5': 1, '45': 1, '345': 1, '2345': 2, '12345': 3}
ex) 111111 => dp = {'1': 1, '11': 2, '111': 3, '1111': 5, '11111': 8, '111111': 13}
중복되는 숫자가 많으면 훨씬 빨라진다~~

---

98. Validate Binary Search Tree

https://leetcode.com/problems/validate-binary-search-tree/

My Answer 1: Wrong Answer (78 / 80 test cases passed.)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def func(root, lr, m):
            if root is None:
                return True
            
            if lr == 0 and m <= root.val:
                return False
            elif lr and m >= root.val:
                return False
            
            a = 1
            if root.left:
                if root.val <= root.left.val:
                    a *= 0
                else:
                    a *= func(root.left, lr, m)
            if root.right:
                if root.val >= root.right.val:
                    a *= 0
                else:
                    a *= func(root.right, lr, m)
            
            return a
        
        return func(root.left, 0, root.val) and func(root.right, 1, root.val)

처음 루트의 왼쪽과 오른쪽을 각각 재귀 돌려줌

m = 가장 처음 루트의 값
lr == 0 왼쪽 편이면 m 값 보다 다 작아야하고
lr == 1 오른쪽 편이면 m 값 보다 다 커야한다는 조건

left 가 root 보다 작을 때, right 가 root 보다 클 때 재귀

머리가 안돌아가네요...

Solution 1: Accepted (Runtime: 44 ms - 69.45% / Memory Usage: 16.5 MB - 53.86%)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def rec(node, left, right):
            if node:
                if node.val <= left or node.val >= right: return False
                return rec(node.left, left, node.val) and rec(node.right, node.val, right)
            return True
        return rec(root, -float('inf'), float('inf') )

노드의 다음 left 는 지금 노드의 값보다 무조건 작아야하니까 right: node.val 로
노드의 다음 right 는 지금 노드의 값보다 무조건 커야하니까 left: node.val 로

left 에는 left: left, right: node.val,
right 에는 left: node.val, right: right

를 넘겨줘서 node.val 가 left ~ right 사이의 값인지 확인

냅다 외워!!!