Leetcode Weekly Contest 311 (2022.09.18) (2413~2416)

Problem 2413, 2414, 2415, 2416.

 

Problem 2413.

 

코드 :

class Solution:
    def smallestEvenMultiple(self, n: int) -> int:
        if n % 2 == 0:
            return n
        else:
            return n * 2

 

Problem 2414 :

코드 : 

class Solution:
    def longestContinuousSubstring(self, s: str) -> int:
        result = 1
        temp = 1
        for i in range(1, len(s)):
            if ord(s[i]) - ord(s[i-1]) == 1:
                temp += 1
                result = max(result, temp)
            else:
                temp = 1
            # print(ord(s[i]) - ord(s[i-1]))
        return result

 

problem 2415 :

코드 : 

# 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:
    d = defaultdict(list)
    
    def traversal(self, node, lvl=0):
        if not node:
            return
        if lvl % 2 == 1:
            self.d[lvl].append(node.val)
        self.traversal(node.left, lvl+1)
        self.traversal(node.right, lvl+1)
        
    def trav2(self, node, lvl=0):
        if not node:
            return 
        if lvl % 2 == 1:
            node.val = self.d[lvl].pop()
        self.trav2(node.left, lvl+1)
        self.trav2(node.right, lvl+1)        
    
    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        self.traversal(root)
        self.trav2(root)
        return root

 

설명 : 두 번의 traversal을 진행합니다. 첫 번째에서는 dictionary를 populate 한 이후,

두 번째 traversal에서는 stack에서 list 들을 pop하면서 tree를 다시 씁니다.

 

problem 2416:

코드 :

class TrieNode:
    def __init__(self, char, val=1, nextnode=None):
        self.char = char
        self.val = val
        self.d = {}
        
    def __str__(self, level=0):
        ret = "\t"*level+repr(self.val)+"\n"
        for k, v in self.d.items():
            ret += str(k)+str(v)
        return ret

class Solution:
    def sumPrefixScores(self, words: List[str]) -> List[int]:
        rootnode = TrieNode("", val=0)
        
        # initialize make trie
        for word in words:
            thisnode = rootnode
            for i in range(len(word)):
                if word[i] in thisnode.d:
                    thisnode.d[word[i]].val += 1
                    thisnode = thisnode.d[word[i]]
                else: # not in trie make!
                    thisnode.d[word[i]] = TrieNode(word[i])
                    thisnode = thisnode.d[word[i]]
        result = []
        # calculate number of trie
        for word in words:
            thisnode = rootnode
            ans = 0
            for i in range(len(word)):
                if word[i] in thisnode.d:
                    ans += thisnode.d[word[i]].val
                    thisnode = thisnode.d[word[i]]
            result.append(ans)
        return result

설명:

이 문제를 처음 보면, dictionary 를 사용해서 모든 prefix들을 담아서 count를 하고 싶은 욕구가 생깁니다.

하지만 실제로 그렇게 해 보면, time limit exceeded가 나오는 걸 볼 수 있습니다.

key값이 10^6이 되고, key중에 10^3이 되는 큰 값이 있어서 그런 것 같습니다.

 

그럼 답은, Trie가 됩니다!

Trie라는 data structure에 대해서 깊게 다루지는 않겠습니다.

단지, 값 하나를 가지는 tree structure 이고, 값을 가지는 정도의 manipulation을 해 줘야될 것 같습니다.

 

첫 번째 for loop 에서는 trie를 만들고

두 번째 for loop 에서 trie를 사용해서 계산합니다.

실제 구현이 좀 복잡하다는 편만 제외하면, 개념은 prefix를 이용한 방법과 크게 다르지 않습니다만,

dummy node처럼 node를 처음에 구성하는 것만 제외하면 그저 dictionary 안에 dictionary를 구성하는 형태라고 할 수 있겠습니다.

다른 분들이 구현한 것을 보니, dictionary이외에 C++같은 경우 포인터를 사용한 경우도 있고, 다양하게 푸는 걸 볼 수 있었습니다.

 

처음 dictionary를 사용한 방법이 왜 time limit exceeded가 나오는지에 대해서 의문이 들었었는데,

hash function을 사용하는 데에 string의 길이가 늘어남에 따라 시간이 많이 들기 때문이라고 합니다!