LeetCode[ 530 | Python ] Minimum Absolute Difference in BST
업데이트:
문제
이미 존재하는 Binery Search Tree에서 root 가 주어졌을 때 임의의 두 노드의 가장 작은 차를 반환해야하는 문제.
풀이
시도 1
실행시간 : 5924ms
메모리 : 19.7MB
가장 먼저 생각나는대로 풀이한 코드.
노드간 가장 작은 차이를 구하기 위해서는 모든 노드를 순회해야 한다.
순회하기 위한 탐색 방법은 dfs를 택했다. 이유는 코드가 간결해질 것으로 판단했기 때문이다.
풀이 방법은 다음과 같다.
- 판단할 기준인 최소 값
min_val, 노드가 가지고 있는 값을 담을hist를 초기화 한다. - 입력으로 들어온 노드의 값을
hist에 저장한다. hist안의 값들 중 차이가 가장 작은 값을 추출한다.- 현재 노드의 왼쪽에 있는 노드를 탐색한다.
- 현재 노드의 오른쪽에 있는 노드를 탐색한다.
- 현재 노드가 존재하지 않으면 종료한다.
- 위 과정을 모든 노드에 대해 재귀적으로 수행한다.
- 최소 차이를 반환한다.
실행에 성공은 했지만 이 코드에 큰 문제가 존재했다.
hist에 담아져있는 값을 중복적으로 탐색한다는 것이다. 이 때문에 실행시간이 폭발적으로 늘어났다고 추정했다.
이를 해결하기 위해 코드를 개선했다.
class Solution(object):
def getMinimumDifference(self, root):
global min_val
hist = []
min_val = float('inf')
def dfs(start):
global min_val
if start == None:
return
hist.append(start.val)
for i in hist[:-1]:
min_val = min(abs(start.val - i), min_val)
dfs(start.left)
dfs(start.right)
dfs(root)
return min_val
개선 1
실행시간 : 60ms
메모리 : 18.7MB
hist에 담긴 값들은 중복적으로 판단될 필요 없다.
따라서 순회를 하며 hist에 모든 값들을 저장하고 그 차이를 반환한다.
한가지 의문이 들었는데, 이 코드를 실행시키면 hist의 원소들은 알아서 정렬된 상태라는 것이다.
이는 BST를 탐색하고, 중위 순회를 사용했기 때문에 가장 작은 값들부터 순서대로 저장하기 때문이다.
결과적으로 처음 시도했던 코드보다 배수 이상으로 적은 시간안에 수행을 완료했다.
번외로, BFS로 트리를 순회했을 경우도 궁금했다.
class Solution:
def getMinimumDifference(self, root):
hist = []
min_val = float('inf')
def dfs(start):
if start == None:
return
dfs(start.left)
hist.append(start.val)
dfs(start.right)
dfs(root)
hist.sort()
for i in range(1, len(hist)):
min_val = min(abs(hist[i] - hist[i-1]), min_val)
return min_val
개선 - 번외 BFS
실행시간 : 58ms
메모리 : 18.7MB
해당 문제를 BFS로 순회하여 풀이했을 경우의 코드이다.
눈에 띄는 실행시간의 차이는 없었지만, 너비 우선 탐색인 만큼 노드의 값을 오름차순으로 담지 않아 정렬을 따로 수행해야한다는 로직에서의 차이가 있다.
from collections import deque
class Solution:
def getMinimumDifference(self, root):
hist = []
min_val = float('inf')
def bfs(start):
q = deque()
q.append(start)
while q:
x = q.popleft()
hist.append(x.val)
if x.left != None:
q.append(x.left)
if x.right != None:
q.append(x.right)
bfs(root)
hist.sort()
for i in range(1, len(hist)):
min_val = min(abs(hist[i] - hist[i-1]), min_val)
return min_val
생각 & 정리
DFS냐, BFS냐는 그래프, 트리 관련된 문제를 맞닥들였을 때 꽤나 고민되는 부분이다.
최단거리를 찾기 위해서는 BFS를 사용하는게, 특정 값을 찾아내는데는 DFS를 사용한다고 하지만 막상 애매모호한 부분들이 많이 생긴다.
사실 이 문제에서는 DFS를 수행하는게 더 효율적이다.
주어진 트리들은 대부분 균형잡히지 않고, 일반적으로 BFS보다 DFS의 메모리 사용량이 queue를 이용하는 BFS 보다 더 적기 때문이다.
또한 BFS를 수행했을 경우 원소들을 다시 정렬해주어야 하는 과정이 포함되어 있어 비효율적이다.
주어진 상황에 따라서 적절한 순회방법을 택하는 것이 좋겠다.
댓글남기기