자바 코딩테스트 강좌, 트리의 부모 찾기

코딩 테스트는 많은 기업에서 필수적으로 요구하는 과정이며, 특히 데이터 구조와 알고리즘에 대한 이해는 핵심 역량으로 자리 잡고 있습니다. 이 글에서는 트리 구조와 그 부모 노드를 찾는 문제를 다룰 것입니다. 이 문제의 중요성과 해결 방법, 그리고 자바로 해결하는 과정을 상세히 설명하도록 하겠습니다.

문제 설명

트리 구조는 노드의 계층적 관계를 나타내는 자료구조입니다. 각 노드는 자식 노드를 가질 수 있으며, 이와 같이 간단한 구조 속에서도 다양한 문제가 발생할 수 있습니다. 이번 문제에서는 주어진 노드의 부모 노드를 찾는 것입니다.

문제 정의

주어진 트리와 특정 노드의 값을 입력받아 해당 노드의 부모 노드를 반환하는 프로그램을 작성하시오. 만약 입력된 노드가 루트 노드이거나 존재하지 않는 경우에는 -1을 반환해야 합니다.

입력 형식

첫 번째 줄: 노드의 개수  (1 ≤ N ≤ 100,000)
두 번째 줄: 각 노드의 부모 노드 정보 (공백으로 구분된 정수로 나타냄)
세 번째 줄: 찾고자 하는 노드

출력 형식

부모 노드의 값 또는 -1

문제 해결 접근 방식

우리는 주어진 트리의 부모 노드를 빠르게 찾기 위해 몇 가지 방법을 사용할 수 있습니다. 주로 사용하는 방법은 배열을 통한 접근입니다. 부모 노드 정보를 배열로 저장하면, 특정 노드의 부모를 상수 시간에 찾을 수 있습니다. 이 과정은 다음과 같습니다:

1. 데이터 구조 선택

노드의 부모 정보를 효과적으로 저장하기 위해, 우리는 배열을 사용할 것입니다. 배열의 인덱스가 노드의 값에 해당하고, 각 인덱스에 저장된 값이 부모 노드의 값입니다. 예를 들어, 노드의 부모 정보가 다음과 같다면:

[-1, 0, 0, 1, 1, 2]

위 배열에서:

  • 노드 0의 부모: -1 (루트 노드)
  • 노드 1의 부모: 0
  • 노드 2의 부모: 0
  • 노드 3의 부모: 1
  • 노드 4의 부모: 1
  • 노드 5의 부모: 2

2. 알고리즘 설계

이제 알고리즘을 설계합니다. 전체 과정은 다음과 같습니다:

  1. 부모 정보를 저장할 배열을 초기화합니다.
  2. 부모 정보 배열을 입력받습니다.
  3. 찾고자 하는 노드를 입력받습니다.
  4. 입력된 노드가 배열의 범위 내에 있는지 확인합니다.
  5. 부모 노드를 찾고 반환합니다.
  6. 부모 노드가 루트 노드일 경우 -1을 반환합니다.

자바 코드 구현

이제 위에서 설명한 알고리즘을 자바로 구현해 보도록 하겠습니다. 우선 필요한 클래스를 정의하고, 메인 메서드를 작성하겠습니다:

import java.util.Scanner;

public class FindParentNode {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 노드의 개수 입력
        int n = sc.nextInt();
        int[] parents = new int[n];
        
        // 부모 정보 입력
        for (int i = 0; i < n; i++) {
            parents[i] = sc.nextInt();
        }
        
        // 찾고자 하는 노드 입력
        int target = sc.nextInt();
        
        // 부모 노드 찾기
        int result = findParent(parents, target);
        System.out.println(result);
        
        sc.close();
    }
    
    // 부모 노드 찾기 메서드
    public static int findParent(int[] parents, int node) {
        if (node < 0 || node >= parents.length) {
            return -1; // 존재하지 않는 노드
        }
        // 부모 노드 반환
        return parents[node];
    }
}

설명

위 코드에서, 우리는 Scanner 클래스를 사용하여 입력을 받고, parents 배열에 부모 정보를 저장합니다. 나중에 목표 노드를 입력받고, findParent 메서드를 호출하여 부모 노드를 찾습니다. 이 메서드는 입력된 노드가 유효한지 확인 후, 해당 노드의 부모를 반환합니다.

테스트 케이스

이제 구현된 코드가 올바르게 작동하는지 확인하기 위해 몇 가지 테스트 케이스를 만들어 보겠습니다.

테스트 케이스 1

입력:

6
-1 0 0 1 1 2
3

출력:

1

테스트 케이스 2

입력:

6
-1 0 0 1 1 2
0

출력:

-1

테스트 케이스 3

입력:

6
-1 0 0 1 1 2
6

출력:

-1

결론

이번 포스팅을 통해 자바로 트리의 부모 노드를 찾는 문제를 해결하는 과정을 살펴보았습니다. 트리 구조는 데이터 구조의 기본 개념 중 하나이며, 기본적인 부모-자식 관계를 이해했으므로 다른 복잡한 트리 문제를 해결하는데도 유용할 것입니다. 코딩 테스트에 대비하기 위해 여러 가지 문제를 풀어보고 자신만의 풀이 과정을 만들어 나가기를 바랍니다.