[문제해결을 위한 창의적 알고리즘] Distance of Nodes (고급, p47)
이 문제는 결국 두 노드의 공통 조상을 찾아 거기까지 도착하는데 필요한 거리를 구하는 문제라고 할 수 있다. 문제의 해설을 읽어 보면 쉽게 이해할 수 있는 문제이다. 해설에서는 재귀적인 방법으로 풀었으나, 여기에는 반복적 접근으로 푼 코드를 공유하고자 한다. Recursive로 동작하는 코드보다 Iterative로 동작하는 코드가 call stack을 위한 메모리 할당이 필요 없으므로, 더 빠르게 동작한다.
import java.util.Scanner;
public class NodeDistance {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int first = 0;
int second = 0;
int fd =0;
int sd = 0;
// 두개의 숫자를 읽음
first = sc.nextInt();
second = sc.nextInt();
sc.close();
// 두 숫자가 같다면 거리는 0
while(first != second) {
// 큰 숫자를 반으로 나눠 부모 노드를 찾음
if (first > second) {
first /=2;
fd++;
}
else {
second /=2;
sd++;
}
}
System.out.println(fd+sd);
return;
}
}
Big O(log n) : n은 입력 받은 두 숫자 중 큰 숫자
GitHub: https://github.com/nevermet/CreativeAlgorithmAdv/blob/master/NodeDistance.java