[문제해결을 위한 창의적 알고리즘] 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

문제해결을 위한 창의적 알고리즘 목록