[4코3파] 1명의 스위프트 개발자가 도망가고 4명의 코틀린 개발자, 3명의 파이썬 개발자의 코딩 테스트 스터디 : 4코3파
START :
[3코1파] 2023.01.04~ (301일차)
[4코1파] 2023.01.13~ (293일차)
[4코3파] 2023.10.01 ~ (31일차)
Today :
2023.10.31 [301일차]
Leetcode Trees hard Tries
[1] 124. Binary Tree Maximum Path Sum
https://leetcode.com/problems/binary-tree-maximum-path-sum/description/
문제 설명
이진 트리에서 경로는 루트 노드에서 시작하여 어떤 노드에서 끝나는 노드들의 시퀀스를 나타낸다.
해당 경로의 노드의 최대합을 반환한다. 이 경로는 임의의 노드에서 시작하고 임의의 노드에서 끝날 수 있음
문제 풀이 방법
dfs로 노드를 타고 내려가면서 재귀적으로 노드를 탐색하고, 현재 노드를 포함한 경우와 포함하지 않은 경우를 따로 고려하면서 최대 경로 합을 업데이트 한다.
내 코드
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def maxPathSum(self, root: Optional[TreeNode]) -> int:
ans = [root.val]
def dfs(node):
if not node:
return 0
leftMax, rightMax = dfs(node.left), dfs(node.right)
leftMax = max(leftMax, 0)
rightMax = max(rightMax, 0)
ans[0] = max(ans[0], node.val+leftMax + rightMax)
return node.val + max(leftMax, rightMax)
dfs(root)
return ans[0] 
[2] 297. Serialize and Deserialize Binary Tree
https://leetcode.com/problems/serialize-and-deserialize-binary-tree/
문제 설명
이진 트리를 이진 트리를 문자열 형태로 저장하는 직렬화(Serialize) 메소드와 저장한 문자열을 이진 트리로 변환하는 역직렬화(Deserialize) 하는 클래스를 구현한다.
문제 풀이 방법
dfs로 serialized (직렬화) 할 때 재귀적으로 pre-order로 방법으로 노드를 리스트에 넣고 해당 리스트를 문자열로 반환함
deserialized(역직렬화) 시에는 위에서 직렬화 형식으로 변환한 문자열을 다시 리스트 형식으로 변환한 뒤, 재귀적으로 pre-order 방향으로 노드를 왼쪽, 오른쪽 붙이면서 최종 노드로 반환함
내 코드
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Codec:
def serialize(self, root):
"""Encodes a tree to a single string.
:type root: TreeNode
:rtype: str
"""
ans = []
def dfs(node):
if not node:
ans.append('N')
return
ans.append(str(node.val))
dfs(node.left)
dfs(node.right)
dfs(root)
return ','.join(ans)
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
vals = data.split(',')
self.i = 0
def dfs():
if vals[self.i]=="N":
self.i+=1
return None
node = TreeNode(int(vals[self.i]))
self.i+=1
node.left = dfs()
node.right = dfs()
return node
return dfs()
Leetcode Tries
[1] 208. Implement Trie (Prefix Tree)
https://leetcode.com/problems/implement-trie-prefix-tree/description/
문제 설명
트라이(Trie) 자료 구조 클래스를 구현한다.
해당 클래스는
insert(word: str): 주어진 문자열 word를 트라이에 삽입함
search(word: str): 주어진 문자열 word가 트라이에 존재하는지 확인함
startsWith(prefix: str): 주어진 접두사(prefix)로 시작하는 어떤 문자열이 트라이에 존재하는지 확인함
의 세 메소드로 구성되어 있다.
문제 풀이 방법
트라이를 구현하려면 뿌리 노드로 시작하는 트라이 클래스를 만들고, 각 노드는 해당 문자, 자식 노드에 대한 링크, 그 문자열이 끝나는 지점을 나타내야 한다.
딕셔너리 자료구조를 갖는 children과 끝문자임을 나타내는 불리언 endOfword를 갖는 TrieNode 클래스를 구현한다.
그리고 단어가 주어지면 문자열 하나당 트라이노드로 생성되는데, insert 시에는 루트 노드에서 children 해쉬 맵을 확인하면서 문자열이 존재하지 않을 경우 자식 노드로 트라이노드를 생성하고, 존재할 경우 넘긴다. search, startwith 와 같이 문자열을 탐색할 때도 루트 노드에서 children 노드를 확인하면서 내려가면서 있는지 유무를 탐색한다.
내 코드
class TrieNode:
def __init__(self):
self.children = {}
self.endOfword = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
cur = self.root
for c in word:
if c not in cur.children:
cur.children[c] = TrieNode()
cur = cur.children[c]
cur.endOfword = True
def search(self, word: str) -> bool:
cur = self.root
for c in word:
if c not in cur.children:
return False
cur = cur.children[c]
return cur.endOfword
def startsWith(self, prefix: str) -> bool:
cur = self.root
for c in prefix:
if c not in cur.children:
return False
cur = cur.children[c]
return True
[2] 211. Design Add and Search Words Data Structure
https://leetcode.com/problems/design-add-and-search-words-data-structure/description/
문제 설명
단어를 추가하고, 검색하는 기능을 가지는 데이터 구조 클래스를 설계하는 것이다.
여기서 검색시 와일드카드 문자(.)가 사용 가능하다.
addWord(word: str): 주어진 단어 word를 데이터 구조에 추가함
search(word: str): 주어진 단어 word가 데이터 구조에 존재하는지 확인함 이때, 와일드카드 문자(.)는 어떤 문자든 하나의 문자에 대응함
위의 해당 메소드를 구현한다.
문제 풀이 방법
나머지 추가의 경우에는 일반 트라이 구조에 넣듯이 구현하면 되는데, 검색 시 와일드카드 문자를 사용할 수 있어서, search 메소드를 잘 구현해야 한다.
와일드카드 문자를 다루는 부분은 dfs를 이용해서 트라이 내에서 재귀적으로 탐색을 수행하여 처리한다.
내 코드
class TrieNode:
def __init__(self):
self.children = {}
self.endOfword = False
class WordDictionary:
def __init__(self):
self.root = TrieNode()
def addWord(self, word: str) -> None:
cur = self.root
for c in word:
if c not in cur.children:
cur.children[c] = TrieNode()
cur = cur.children[c]
cur.endOfword = True
def search(self, word: str) -> bool:
def dfs(i, root):
cur = root
for j in range(i, len(word)):
c = word[j]
if c == '.':
for child in cur.children.values():
if dfs(j+1, child):
return True
return False
else:
if c not in cur.children:
return False
cur = cur.children[c]
return cur.endOfword
return dfs(0, self.root)
[3] 212. Word Search II
문제 설명
2차원 그리드(board)에서 주어진 단어 목록을 찾는 문제이다.
주어진 그리드에서 단어 목록에 있는 단어들을 찾는데, 각 단어는 그리드 내에서 인접한 문자들로 구성되어야 한다.
이때 단어는 수직 또는 수평 방향으로만 구성될 수 있으며, 한 문자를 여러 번 사용할 수 없다.
문제 풀이 방법
해당 문제는 백트래킹(backtracking)과 트라이로 구현 한다.
주어진 단어들을 트라이 자료 구조에 넣는 트라이 클래스를 구현하고,
아래에 dfs로 주어진 board를 서치하면서, board 내의 그리디를 사방(수직, 수평)으로 이동하면서 트라이로 구현했던 단어사전에 있는 단어들과 맞으면 리스트에 넣어 업데이트 한다.
내 코드
class TrieNode:
def __init__(self):
self.children = {}
self.endOfword = False
def addWord(self, word):
cur = self
for c in word:
if c not in cur.children:
cur.children[c] = TrieNode()
cur = cur.children[c]
cur.endOfword = True
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
root = TrieNode()
for c in words:
root.addWord(c)
ROWS, COLS = len(board), len(board[0])
ans, visited = set(), set()
def dfs(r,c,node,word):
if r<0 or c<0 or r==ROWS or c==COLS or (r,c) in visited or board[r][c] not in node.children:
return
visited.add((r,c))
node = node.children[board[r][c]]
word += board[r][c]
if node.endOfword:
ans.add(word)
dfs(r-1,c, node, word)
dfs(r+1,c, node, word)
dfs(r,c-1, node, word)
dfs(r,c+1, node, word)
visited.remove((r,c))
for r in range(ROWS):
for c in range(COLS):
dfs(r,c, root, '')
return list(ans)
여담
와 7월에 하루 내내 했었어서 그런지
다시 보니까 ㄱ 나고 한번에 이해 완~ 굿~
