LeetCode [ 230 | Python ] Kth Smallest Element in a BST
업데이트:
문제
이미 존재하는 BST(Binary Search Tree)에서 정수 k 와 root 가 주어지면 BST 내에서 k번째로 작은 값을 반환해야 하는 문제.
풀이
시도
실행시간 : 30ms
메모리 : 21MB
주어진 BST를 중위 순회로 모두 순회하며 값을 저장한 후 k 번째 값을 반환하는 코드
가장 바로 떠올리고, 간단하게 짤 수 있는 솔루션이었다.
굳이 중위순회를 택한 이유는, 가장 왼쪽(가장 작은 값) 부터 시작해서 로직을 중간에 처리하기 위함이었다.
다만 이 코드는 항상 노드의 개수만큼 순회를 수행해야하므로 k번째 값을 찾고 난 후로도 함수가 종료되지 않는면에서 비효율적인 솔루션이다.
이를 아래에서 개선했다.
class Solution(object):
def kthSmallest(self, root, k):
hist = []
min_val = float('inf')
def dfs(start):
if start == None:
return
dfs(start.left)
hist.append(start.val)
dfs(start.right)
dfs(root)
return hist[k-1]
개선
실행시간 : 24ms
메모리 : 21MB
전체적으로 중위순회를 통해 k번째 작은 수를 반환하는 것은 같다.
하지만 중간 노드를 탐색할 때 cnt 변수를 통해 몇 번째인지 세어주고, 현재 cnt의 값이 k와 같다면 바로 함수를 종료하고 그 값을 반환할 수 있게 변경했다.
class Solution(object):
def kthSmallest(self, root, k):
global cnt
cnt = 0
def dfs(start):
global cnt
if start == None:
return None
l = dfs(start.left)
if l != None:
return l
cnt += 1
if cnt == k:
return start.val
r = dfs(start.right)
if r != None:
return r
return None
return dfs(root)
생각 & 정리
global 변수를 최대한 사용하고 싶지 않았다.
global 변수를 사용하면 가독성, 결합도가 증가된다는게 이유인데 (알고리즘 문제지만 코딩 습관도 잘 가져가고 싶다.)
cnt 변수의 경우 전달하는 식으로 해결하려 했는데, 반환되는 튜플이 점점 늘어나거나 None을 반환해서 global 변수를 사용했다.
global 변수를 사용하지 않고 해결하는 방법은 무엇이 있었을까?
(이를 알아내기 위해서 gpt와 많은 상담시간을 가졌다..)
그 중 하나는 인자 전달 방식을 이용하는 것이다.
일단 이 문제는 python의 인자 전달 방식으로 생기는 문제이다.
- 값에 의한 호출
- 참조에 의한 호출
간단하게 말하자면 값에 의한 호출은 해당 값의 복사본이 함수로 전달되기 때문에 전달받은 값을 조작해봤자 아무런 변화가 없다.
따라서 함수 밖의 값을 조작하기 위해서는 2번의 참조에 의한 호출을 사용해야 한다.
참조에 의한 호출은 그 변수의 메모리 주소를 전달하기 때문에 값을 변경할 수 있다.
애초에 스택을 사용했으면 이런 문제에 크게 매달리지 않았을 것 같지만, 문제를 회피하기 보다는 직면에 보고싶었다.
알고리즘을 풀기위해 습득했던 Python이지만, 은근 어려우면서도 매력있는 언어인 것 같다.
댓글남기기