[문제]
https://school.programmers.co.kr/learn/courses/30/lessons/42892
[풀이]
직접 이진트리를 구성한 뒤, preorder과 postorder를 돌리면 된다.
[코드]
import java.util.*;
class Solution {
int idx;
public int[][] solution(int[][] nodeinfo) {
int[][] answer = {};
//전위 순회, 후위 순회한 결과를 2차원 배열에 순서대로 담아 return
Node[] nodes = new Node[nodeinfo.length];
for(int i=0; i<nodeinfo.length; i++){
nodes[i] = new Node(i+1, nodeinfo[i][0], nodeinfo[i][1], null, null);
}
//y값이 큰 순서대로, 같으면 x값이 작은 순서대로
Arrays.sort(nodes, new Comparator<Node>(){
@Override
public int compare(Node n1, Node n2){
if(n1.y==n2.y){
return n1.x-n2.x;
}
else return n2.y-n1.y;
}
});
//이진 tree 만들기
Node parent = nodes[0];
for(int i=1; i<nodes.length; i++){
insertNode(parent, nodes[i]);
}
answer = new int[2][nodes.length];
Node root = nodes[0];
idx = 0;
preorder(root, answer);
idx = 0;
postorder(root, answer);
return answer;
}
public void insertNode(Node parent, Node child){
if(parent.x > child.x){
if(parent.left==null) parent.left = child;
else insertNode(parent.left, child);
}
else{
if(parent.right==null) parent.right = child;
else insertNode(parent.right, child);
}
}
public void preorder(Node node, int[][] answer){
if(node!=null){
answer[0][idx++] = node.num;
preorder(node.left, answer);
preorder(node.right, answer);
}
}
public void postorder(Node node, int[][] answer){
if(node!=null){
postorder(node.left, answer);
postorder(node.right, answer);
answer[1][idx++] = node.num;
}
}
class Node{
int num, x, y;
Node left;
Node right;
Node(int num, int x, int y, Node left, Node right){
this.num = num;
this.x = x;
this.y = y;
this.left = left;
this.right = right;
}
}
}
'알고리즘 공부 및 문제 풀이 > 프로그래머스(PRO)' 카테고리의 다른 글
[pro] 프로그래머스 level3 42893 매칭 점수 (Java) - 문자열, 정규식 (0) | 2023.01.25 |
---|---|
[pro] 프로그래머스 level3 60063 블록 이동하기 (Java) - BFS, 시뮬레이션 (0) | 2023.01.20 |
[pro] 프로그래머스 level3 42861 섬 연결하기 (Java) - MST (0) | 2023.01.19 |
[pro] 프로그래머스 level3 42884 단속카메라 (Java) - 그리디 (0) | 2023.01.18 |
[pro] 프로그래머스 level3 42895 N으로 표현 (Java) - dp (0) | 2023.01.18 |