책너두 (코딩 인터뷰 완전분석) 46일차 (17.12, 17.15)

17. 어려운 연습문제

17.12 BiNode

• BiNode라는 간단한 자료구조가 있다. 이 자료구조 안에는 다른 두 노드에 대한 포인터가 들어 있따.

public class BiNode {
    public BiNode node1, node2;
    public int data;
}

• BiNode 자료구조는 이진 트리를 표현하는 데 사용될 수도 있고(node1은 왼쪽 노드를, node2는 오른쪽 노드를 가리키게 만들면 된다), 양방향 연결리스트를 만드는 데 사용할 수도 있다(node1은 이전 노드를, node2는 다음 노드를 가리키게 만든다). BiNode를 사용해서 구현된 이진 탐색 트리를 양방향 연결리스트로 변환하는 메서드를 작성하라. 값의 순서는 유지되어야 하며 모든 연산은 원래 자료구조 안에서(in-place) 이루어져야 한다.

17.15 가장 긴 단어

• 주어진 단어 리스트에서, 다른 단어들을 조합하여 만들 수 있는 가장 긴 단어를 찾는 프로그램을 작성하라.