3주간의 컴퓨터 사이언스 과정이 끝나고 맞게된 첫 코딩테스트는 BST를 응용한 주제로 문제가 나왔다.
해당 주제에 대해서 재밌게 과제를 풀었기에 BST 의 contains 또는 insert 관련한 문제가 나온다면 좋겠다 생각했지만.. 이는 아주 큰 오산이었다..
비슷한 문제라기보다는 해당 개념을 이해하고 그것을 더 응용해야하는 문제가 나와서 문제 의도는 빠르게 파악했지만 주어진 시간 안에 코드를 구현해내지 못했다.. 😱
문제
주어진 두 개 노드의 공통 부모인 ken을 찾기
처음의 ken을 찾는 것이라 그래서 console에 트리 구조를 찍어보기 전까지는 value 값 자체가 ken인건가~? 했는데 그냥 두 노드의 공통 부모인 5를 반환해야 하는 문제였다.
value가 ken이었다면 두 노드를 자식으로 가지고 있는지 판단을 안해도 되니 의미가 없긴 하겠다.
ken is 5..
문제는 아래와 같다.
[요구사항]
주어진 BST 내에서 주어진 2개의 노드의 "켄" 노드를 찾아 반환해야 합니다.
2개의 노드가 주어졌을때 "켄" 노드란 아래 조건을 충족하는 노드입니다.
- 주어진 2개의 노드로부터 가장 가까운 부모 노드입니다.
- 부모 노드란, 자기 자신을 포함합니다.
// 생성자 함수
function BinarySearchTree(value) {
this.value = value; // 인스턴스..
this.left = null;
this.right = null;
}
// ✅ 프로토타입 메서드가 아닌 static method
BinarySearchTree.findKen = function (root, a, b) {
// TODO: Your solution..
// 여기서 한 번 더 유심히 봐야할 부분은 insert와 contains methods는
// prototype method지만 해당 findken은 static method라는 점이다.
};
// 프로토타입 메서드 -> 생성자함수 BST의 인스턴스인 value, left, right를 쓸 수 있다.
BinarySearchTree.prototype.insert = function (value) {
const node = new BinarySearchTree(value);
if (value < this.value) {
if (this.left) {
this.left.insert(value);
} else {
this.left = node;
}
} else {
if (this.right) {
this.right.insert(value);
} else {
this.right = node;
}
}
};
// 프로토타입 메서드
BinarySearchTree.prototype.contains = function (value) {
if (value === this.value) {
return true;
}
if (value < this.value) {
if (this.left) {
return this.left.contains(value);
}
}
if (value > this.value) {
if (this.right) {
return this.right.contains(value);
}
}
return false;
};
문제에서 트리의 구조는 아래 사진과 같다.
해당 문제를 서치해보니, Lowest Common Ancestor of a Binary Search Tree
즉 LCA를 찾는 문제로 불리는 것을 알게 되었다.
LCA란 주어진 두 노드 a, b에 대해서 a, b를 자손으로 갖는(자기 자신은 자기의 자손이라고 본다) 가장 가까운 부모노드 ken을 의미하는 것이다.
예를 들어,
위 사진의 BST에서 5와 15의 LCA는 10이다. 다른 예로 5와 7의 LCA는 5이다.
왜냐하면 자기 자신도 자손으로 생각할 수 있다고 했기 때문에 가장 가까운 부모 노드는 5가 되는 것이다.
주어진 조건에서 부모 노드란, 자기 자신을 포함한다는 말 뜻이 이 뜻이었구나,,
해당 문제에서
a = 6,b = 1이므로 우리가 찾아야 하는 공통 부모는 결국5가 된다.
이 문제를 접근하기 위해서 가장 먼저 생각해야 할 것은 BST의 특징인데, BST는 해당 노드에서 왼쪽 후손들은 전부 그 노드보다 작은 값을 갖고, 오른쪽 후손들은 전부 그 노드보다 큰 값을 갖는다.
따라서 이를 이용하면 몇 가지 경우를 생각할 수 있다.
1. 현재 노드가 주어진 두 노드 중 하나일 경우 => 이 경우에 더 수색할 필요가 없다.
결국 다른 한 노드는 지금 노드의 자식들 중 하나일 것이기 때문에 현재 노드가LCA가 된다.
위에서 말한5와7의 관계가 이에 해당한다.
2. 현재 노드가 주어진 두 노드 값의 사이에 위치할 경우b < current node < a=>
이 경우에도 더 수색할 필요가 없다.
현재 노드를 기준으로 왼쪽 자식에 더 작은 노드(b = 1)가, 오른쪽 자식에 더 큰 노드(a = 6)가 존재할 것이기 때문에, 지금 노드가LCA이다.
이 말 뜻도 잘 이해가 가지 않았는데 위 그림을 예로 들면b가 3이고a가 7일 경우 현재 노드가 그 사이에 위치 하게 된다면 , 현재 노드(5)가 곧LCA가 되는 것이다.
3. 마지막 경우로,
현재 노드가 두 노드 값보다 클 경우 => 왼쪽 자식으로 내려가서 더 수색한다. 두 노드는 결국 현재 노드보다 값이 작으므로 왼쪽 자식에 위치해 있을 수 밖에 없다.
반대로 현재 노드가 두 노드 값보다 작을 경우 => 오른쪽 자식으로 내려가서 더 수색한다.
1과 2에 조건을 만날 때까지 이를 반복한다.
위 로직을 코드로 구현하면 아래와 같다.
let left;
let right;
if (root.value === a.value || root.value === b.value) {
return root; // 위 에서 말했듯이 현재 노드가 둘 중 하나일 시에 현재 노드가 공통 부모가 된다.
}
if (root.left) { // 위 조건에 속하지 않고 현재 노드의 왼쪽 자식이 존재한다면 left에 아래와 같이 재할당해준다. left를 기준으로 재귀
left = this.findKen(root.left, a, b);
}
if (root.right) { // 반대로 첫 번째 조건에 속하지 않고 현재 노드의 오른쪽 자식이 존재할 시 right에 재할당. right를 기준으로 재귀
right = this.findKen(root.right, a, b);
}
if (left && right) { // 2번 경우의 수와 같이 왼쪽자식과 오른쪽 자식에 동시에 존재하게 되면 결국 현재 노드는 그 사잇 값이 되므로 현재 노드인 root가 곧 공통부모가 된다
return root;
} else if (left) { // 1번 경우에 해당
return left;
} else if (right) { // 1번 경우에 해당
return right;
}재귀함수를 타기 때문에 root가 곧 현재 노드가 된다.
다른 풀이에서는 Math.min/max 메서드를 이용하여 주어진 두 노드 중 가장 큰 값/작은 값이 현재 노드보다 작거나 클 때를 이용해서 풀기도 하였는데 해당 문제를 더 복습해 본 뒤에 다른 여러 풀이로도 접근해보아야겠다.
static method란?
"prototype"이 아닌 클래스 함수 자체에 메서드를 설정할 수 있는 것을 말한다.
BinarySearchTree.prototype.contains
BinarySearchTree.findKen -> 클래스 함수 자체에 메서드 설정- 인스턴스를 생성하지 않아도 호출 할 수 있는 메서드이다.
(주어진 코드에서 인스턴스는 아래와 같이this.value / this.left / this.right에 해당한다.)
function BinarySearchTree(value) {
this.value = value; // 인스턴스..
this.left = null;
this.right = null;
}-
static method는 클래스 (위에선 BST에 해당) 와 연결되어 있지만, 해당 클래스의 특정 인스턴스와는 연결되어 있지 않다. 이러한 메서드에는 클래스의 객체가 입력 인수로 필요하지 않다고 한다. 따라서, 클래스의 객체를 생성하지 않고 정적 메서드를 호출할 수 있다.
뭔소린지 아직까진 모르겠다^^ -
정적 메서드를 정의하는 이유
정적 메서드는 코드를 실행하기 전에 클래스의 인스턴스를 생성하지 않으려는 경우에 유용하다고 한다.
그 외)
자바스크립트는 프로토타입 기반 객체지향 언어이다.
프로토타입 기반 객체지향 언어는 클래스가 필요 없는 객체지향 프로그래밍 언어다. 따라서 클래스 없이도 생성자 함수와 프로토타입을 통해 객체지향 언어의 상속을 구현할 수 있다. 여태 바코에서 계속해서 구현해왔던 과제들과 위에 주어진 문제의 메서드들이 이에 포함된다.
다음에 좀 더 살펴볼 개념은..
