[프로그래머스] 길 찾기 게임 (JAVA)

• https://school.programmers.co.kr/tryouts/71897/challenges

  

  

  

  

의식의 흐름

다음과 같은 방식으로 문제를 풀어야겠다고

1. nodeinfo[][]를 통해 tree 만들기

2. 재귀적으로 전위 순회하기

3. 재귀적으로 후위 순회하기

4. 정답 return하기

어떻게 tree를 만들지에 대한 고민이 많았음

⇒ y값을 기준으로 내림차순 정렬하기

⇒ 0번 idx를 root로 하여 하나씩 left, right setting 해주며 tree 만들기

---

Solve.

import java.util.*;

class Solution {
    class Node{
        int x, y;
        int data;
        
        Node left;
        Node right;
        
        Node(int x, int y, int data){
            this.x = x;
            this.y = y;
            this.data = data;
        }
        
        public String toString(){
            return "x : " + x + " // y : " + y + " // data : " + data;
        }
    }
    
    private Node[] nodeArray;
    private List<Integer> preorderList = new ArrayList<>();
    private List<Integer> postorderList = new ArrayList<>();
    
    public int[][] solution(int[][] nodeinfo) {
        init(nodeinfo);
        
        nodeArraySort();
        
        Node tree = makeTree();
        
        // 순회
        setPreorderList(tree);
        setPostorderList(tree);
        
        return getAnswer();
    }
    
    private void init(int[][] nodeinfo){
        nodeArray = new Node[nodeinfo.length];
        for(int i = 0; i < nodeArray.length; i++){
            int[] thisNodeInfo = nodeinfo[i];
            
            nodeArray[i] = new Node(thisNodeInfo[0], thisNodeInfo[1], i + 1);
        }        
    }
    
    private void nodeArraySort(){
        Arrays.sort(nodeArray, new Comparator<Node>(){
            public int compare(Node o1, Node o2){
                if(o2.y == o1.y){
                    return o1.x - o2.x;
                }
                return o2.y - o1.y;
            }
        });        
    }
    
    private Node makeTree(){
        Node tree = nodeArray[0];
        
        for(int i = 1; i < nodeArray.length; i++){
            setTree(tree, nodeArray[i]);
        }
        
        return tree;
    }
    
    private void setPreorderList(Node node){
        preorderList.add(node.data);
        if(node.left != null){
            setPreorderList(node.left);
        }
        if(node.right != null){
            setPreorderList(node.right);
        }        
    }
    
    private void setPostorderList(Node node){
        if(node.left != null){
            setPostorderList(node.left);
        }
        if(node.right != null){
            setPostorderList(node.right);
        }
        postorderList.add(node.data);
    }    
    
    private void setTree(Node parent, Node node){
        if(node.x < parent.x){
            if(parent.left == null){
                parent.left = node;
                return;
            }
            setTree(parent.left, node);
        }else if(parent.x < node.x){
            if(parent.right == null){
                parent.right = node;
                return;
            }            
            setTree(parent.right, node);
        }
    }
    
    private void debugPrint(){
        for(int i = 0 ; i < nodeArray.length; i++){
            System.out.println(nodeArray[i]);
        }
    }
    
    private int[][] getAnswer(){
        int[][] answer = new int[2][];
        
        // preorder
        int[] preorder = new int[preorderList.size()];
        for(int i = 0 ; i < preorder.length; i++){
            preorder[i] = preorderList.get(i);
        }
        
        // postorder
        int[] postorder = new int[postorderList.size()];
        for(int i = 0 ; i < postorder.length; i++){
            postorder[i] = postorderList.get(i);
        }        
        
        // set
        answer[0]= preorder;
        answer[1]= postorder;
        
        return answer;
    }
}

Detail.

1. nodeinfo[][]를 통해 tree 만들기
   1. node 배열 만들기

      nodeArray = new Node[nodeinfo.length];
      for(int i = 0; i < nodeArray.length; i++){
          int[] thisNodeInfo = nodeinfo[i];
          
          nodeArray[i] = new Node(thisNodeInfo[0], thisNodeInfo[1], i + 1);
      }        

   2. y를 기준으로 오름차순 정렬하기

      Arrays.sort(nodeArray, new Comparator<Node>(){
          public int compare(Node o1, Node o2){
              if(o2.y == o1.y){
                  return o1.x - o2.x;
              }
              return o2.y - o1.y;
          }
      });

   3. node[0]을 root로 tree 만들기 (recursively)

      private Node makeTree(){
          Node tree = nodeArray[0];
          
          for(int i = 1; i < nodeArray.length; i++){
              setTree(tree, nodeArray[i]);
          }
          
          return tree;
      }
      
      private void setTree(Node parent, Node node){
          if(node.x < parent.x){
              if(parent.left == null){
                  parent.left = node;
                  return;
              }
              setTree(parent.left, node);
          }else if(parent.x < node.x){
              if(parent.right == null){
                  parent.right = node;
                  return;
              }            
              setTree(parent.right, node);
          }
      }

2. 전위순회

private void setPreorderList(Node node){
    preorderList.add(node.data);
    if(node.left != null){
        setPreorderList(node.left);
    }
    if(node.right != null){
        setPreorderList(node.right);
    }        
}

3. 후위순회 (생략)

4. 정답 return하기

private int[][] getAnswer(){
    int[][] answer = new int[2][];
    
    // preorder
    int[] preorder = new int[preorderList.size()];
    for(int i = 0 ; i < preorder.length; i++){
        preorder[i] = preorderList.get(i);
    }
    
    // postorder
    int[] postorder = new int[postorderList.size()];
    for(int i = 0 ; i < postorder.length; i++){
        postorder[i] = postorderList.get(i);
    }        
    
    // set
    answer[0]= preorder;
    answer[1]= postorder;
    
    return answer;
}