힙
들어가기 전에
힙(heap) 이란?
힙은 트리 기반의 자료 구조로, 부모 노드가 자식 노드보다 항상 작아야 한다. 좌우 노드간의 관계를 정의한 이진 탐색 트리(BST)와는 달리 부모와 자식 노드간의 관계만 정의하고 좌우 노드간의 관계는 정의하지 않는다는 것이 특징이다.
Question 55: 배열의 k번째 큰 요소
정렬되지 않은 배열에서 k번째 큰 요소를 출력하라
입력: nums = [3,2,3,1,2,4,5,5,6], k = 4
출력: 4
내 풀이
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
nums.sort()
return nums[-k]
- 원래는 힙을 사용하는 것이 이 문제의 목표이나 힙을 사용하지 않고서 엄청나게 간단히 풀 수 있었다.
풀이 1: heapq 모듈 이용
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
heap = list()
for n in nums:
heapq.heappush(heap, -n)
for _ in range(1,k):
heapq.heappop(heap)
return -heapq.heappop(heap)
중요 내용
- heapq 모듈은 최소 힙만 지원하므로 음수로 저장한 다음 가장 낮은 수부터 추출해 부호를 변환하면 최대 힙처럼 동작하도록 구현할 수 있다.
풀이 2: heapq 모듈의 heapify 이용
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
heapq.heapify(nums)
for _ in range(len(nums) - k):
heapq.heappop(nums)
return heapq.heappop(nums)
중요 내용
- heapify는 자료구조를 힙 구조로 바꿔주는 연산이다.
풀이 3: heapq 모듈의 nlargest 이용
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
# 입력값이 nums = [3,2,1,5,6,4], k = 2 일때 [6,5]를 리턴함
return heapq.nlargest(k,nums)[-1]
중요 내용
- nlargest() 함수는 k번째만큼 큰 값이 가장 큰 값부터 순서대로 리스트로 리턴된다. nsmallest() 함수 또한 마찬가지로 k번째 작은 값을 리스트로 리턴한다.
Question 56: 트라이(Trie) 구현 (재풀이)
트라이의 insert, search, startsWith 메소드를 구현하라
입력: [“Trie”, “insert”, “search”, “search”, “startsWith”, “insert”, “search”] [[], [“apple”], [“apple”], [“app”], [“app”], [“app”], [“app”]]
출력: [null, null, true, false, true, null, true]
내 풀이
class Trie:
def __init__(self):
self.trieList = []
def insert(self, word: str) -> None:
self.trieList.append(word)
def search(self, word: str) -> bool:
if word in self.trieList:
return True
else:
return False
def startsWith(self, prefix: str) -> bool:
for word in self.trieList:
if prefix in word:
return True
return False
- 직관적으로 풀었으나 startsWith이 모든 단어를 하나씩 검사하므로 O(n) 만큼의 시간 복잡도가 걸려 그리 효과적이지 않은 방법이라 할 수 있다.
풀이 결과
특정 입력값에서 이해할 수 없는 에러가 발생하였다.
풀이 1: 딕셔너리를 이용해 간결한 트라이 구현
class TrieNode:
def __init__(self):
self.word = False
self.children = collections.defaultdict(TrieNode)
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
node = self.root
for char in word:
node = node.children[char]
node.word = True
def search(self, word: str) -> bool:
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return node.word
def startsWith(self, prefix: str) -> bool:
node = self.root
for char in prefix:
if char not in node.children:
return False
node = node.children[char]
return True
중요 내용
-
다음과 같은 형태로 문자가 저장된다.
-
값이 존재하는지 여부를 확인하기 위해서는 깊이 탐색을 하여 search()인 경우에는 해당 노드의 word 값이 참인지 여부를 파악하고 startsWith()인 경우에는 prefix에 해당하지 않는 문자를 찾을 때까지 탐색한다.
Question 57: 팰린드롬 페어
단어 리스트에서 words[i] + words[j]가 팰린드롬이 되는 모든 인덱스 조합 (i,j)를 구하라
입력: words = [“abcd”,”dcba”,”lls”,”s”,”sssll”]
출력: [[0,1],[1,0],[3,2],[2,4]]
내 풀이
class Solution:
def palindromePairs(self, words: List[str]) -> List[List[int]]:
def checkPalindrome(word):
return word == word[::-1]
palindrome_index = []
for i in range(0,len(words)-1):
for j in range(i+1, len(words)):
combined_word1 = words[i]+words[j]
combined_word2 = words[j]+words[i]
if checkPalindrome(combined_word1):
palindrome_index.append([i,j])
if checkPalindrome(combined_word2):
palindrome_index.append([j,i])
return palindrome_index
- 브루트 포스 방법으로 풀었다.
- 시간 복잡도가 $O(n^2)$가 나와 타임아웃이 발생하였다.
풀이 1: 재귀 구조로 중위 순회
class Solution:
prev = -sys.maxsize
result = sys.maxsize
def minDiffInBST(self, root: Optional[TreeNode]) -> int:
if root.left:
self.minDiffInBST(root.left)
self.result = min(self.result, root.val - self.prev)
self.prev = root.val
if root.right:
self.minDiffInBST(root.right)
return self.result
중요 내용
- 다음과 같은 과정으로 계산 과정이 이루어진다.
2. 여기서는 재귀구조로 중위 순회하는 방법으로 풀었다.
풀이 2: 반복 구조로 중위 순회
class Solution:
def minDiffInBST(self, root: Optional[TreeNode]) -> int:
prev = -sys.maxsize
result = sys.maxsize
stack = []
node = root
while stack or node:
while node:
stack.append(node)
node = node.left
node = stack.pop()
result = min(result, node.val - prev)
prev = node.val
print(node.val)
node = node.right
return result
중요 내용
- 풀이 1과 과정은 같으나 재귀구조가 아닌 while문을 사용한 반복 구조로 문제를 풀었다.
트리 순회
-
트리 순회: 그래프 순회의 한 형태로써 트리 자료구조에서 각 노드를 정확히 한번 방문하는 과정을 말한다.
- 트리 순회는 노드의 방문 순서에 따라 다음과 같이 3가지 방식으로 구분된다.
- 전위 순회: N -> L -> R
- 중위 순회: L -> N -> R
- 후위 순회: L -> R -> N
- 트리 순회는 재귀 구현이 훨씬 더 간단하고 직관적이다.
예제
[F, B, G, A, D, null, I, null, null, C, E, H, null] 에 각각의 트리 순회를 적용하였을 때 결과이다.
- 전위 순회
def preorder(node):
if node is None:
return
print(node.val)
preorder(node.left)
preorder(node.right)
preorder(root)
F, B, A, D, C, E, G, I, H
2. 중위 순회
def preorder(node):
if node is None:
return
preorder(node.left)
print(node.val)
preorder(node.right)
preorder(root)
A, B, C, D, E, F, G, H, I
3. 후위 순회
def preorder(node):
if node is None:
return
preorder(node.left)
preorder(node.right)
print(node.val)
preorder(root)
A, C, E, D, B, H, I, G, F
- print()의 위치만 잘 기억하면 전위/ 중위/ 후위를 잘 구분할 수 있을 것이다.
Question 54: 전위, 중위 순회 결과로 이진 트리 구축
트리의 전위, 중위 순회 결과를 입력값을 받아 이진 트리를 구축하라.
입력: 전위: [3,9,20,15,7] 후위: [9,3,15,20,7]
출력: [3,9,20,null,null,15,7]
내 풀이
- 전위와 중위의 연관성을 찾지 못해 한가지 입력값만 사용하여 풀려고 했으나 풀리지 않았다.
풀이 1: 전위 순회 결과로 중위 순회 분할 정복
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
if inorder:
index = inorder.index(preorder.pop(0))
node = TreeNode(inorder[index])
node.left = self.buildTree(preorder, inorder[:index])
node.right = self.buildTree(preorder, inorder[index+1:])
return node
중요 내용
- 전위 순회의 결과로 중위 순회를 인덱싱하여 분할시킨 값을 재귀 호출하며 풀었다.
- 전위 순회의 결과는 중위 순회 결과를 왼쪽과 오른쪽으로 분할시키는 역할을 한다.
Comments