문제

문제 바로가기

풀이

1. 모든 노드를 y좌표가 큰 순 - y좌표가 같다면 x좌표가 적은 순으로 정렬한다.
   -> 트리를 이루는 순서대로 정렬
2. 정렬된 노드를 하나씩 트리에 삽입한다. 이 때, x좌표를 키로 하는 이진 검색 트리의 삽입 알고리즘을 따른다.
3. 완성된 트리를 전위순회, 후위순회하여 정답을 도출한다.

트리를 이루는 순서대로 정렬한다는 의미는,

nodeinfo로 주어지는 1-2-3-4-5-6-7-8-9 순서의 노드들을
위 그림의 7-4-2-6-1-3-9-8-5 순서대로 정렬한다는 뜻이다.

문제를 풀면서 아 이거 무슨 자료구조였는데 이름이 뭐였지 ... 했는데 이진 검색 트리 였다 허허

제출 코드

import java.util.Arrays;

class Solution {
  static int[] preorder;
  static int[] postorder;
  static int idx;
  static class Node implements Comparable<Node> {
    int number;
    int x;
    int y;
    Node parent;
    Node leftChild;
    Node rightChild;
    public Node(int number, int x, int y) {
        this.number = number;
        this.x = x;
        this.y = y;
    }
    public void setParent(Node parent) {
    this.parent = parent;
    }
    public void setLeftChild(Node leftChild) {
        this.leftChild = leftChild;
    }
    public void setRightChild(Node rightChild) {
        this.rightChild = rightChild;
    }
    @Override
    public int compareTo(Node node) {
      if(this.y == node.y) {
        return this.x - node.x;
      } else {
        return node.y - this.y;
      }
    }
  }

  static public int[][] solution(int[][] nodeinfo) {
    Node[] nodeList = new Node[nodeinfo.length];
    for(int i=0; i<nodeinfo.length; i++) {
      nodeList[i] = new Node(i+1, nodeinfo[i][0], nodeinfo[i][1]);
    }
    Arrays.sort(nodeList);
    Node root = nodeList[0];
    for(int i=1; i<nodeList.length; i++) {
      insertNode(root, nodeList[i]);
    }

    preorder = new int[nodeinfo.length];
    postorder = new int[nodeinfo.length];
    idx = 0;
    markPreorder(root);
    idx = 0;
    markPostorder(root);
    int[][] answer = new int[2][];
    answer[0] = preorder;
    answer[1] = postorder;
    return answer;
  }

  static public void insertNode(Node parent, Node newNode) {
    if(parent.x > newNode.x) {
      if(parent.leftChild == null) {
        parent.setLeftChild(newNode);
        newNode.setParent(parent);
      } else {
        insertNode(parent.leftChild, newNode);
      }
    } else {
      if(parent.rightChild == null) {
        parent.setRightChild(newNode);
        newNode.setParent(parent);
      } else {
        insertNode(parent.rightChild, newNode);
      }
    }
  }

  static public void markPreorder(Node node) {
    if(node == null) return;
    preorder[idx++] = node.number;
    markPreorder(node.leftChild);
    markPreorder(node.rightChild);
  }

  static public void markPostorder(Node node) {
    if(node == null) return;
    markPostorder(node.leftChild);
    markPostorder(node.rightChild);
    postorder[idx++] = node.number;
  }
} 

---

구현하고 보니 parent는 필요없다
지워버리자 ,,