프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
class를 사용하여 이진 탐색 트리 구현하기
y가 같을 때(level이 같을 때) x좌표는 오름차순으로.
이외에는 y좌표 내림차순으로
import java.io.*;
import java.util.*;
class Node{
Node right;
Node left;
int value;
int x;
int y;
public Node(int value, int x, int y, Node right, Node left) {
this.value = value;
this.x = x;
this.y = y;
this.right = right;
this.left = left;
}
public int compareTo(Node n1, Node n2) {
if(n1.y == n2.y) return n1.x-n2.x; //오름차순
return n2.y-n1.y; //는 내림차순. 클 수록 루트에 가까움
}
}
class Solution {
public static int[][] answer = {};
public static int idx = 0;
public static void tree(Node parent, Node now) {
if(parent.x < now.x) {
if(parent.right == null)
parent.right = now;
else
tree(parent.right, now);
}
else {
if(parent.left == null)
parent.left = now;
else
tree(parent.left, now);
}
}
public static void preOrder(Node now) {
if(now == null)
return;
answer[0][idx++] = now.value;
preOrder(now.left);
preOrder(now.right);
}
public static void postOrder(Node now) {
if(now == null)
return;
postOrder(now.left);
postOrder(now.right);
answer[1][idx++] = now.value;
}
public int[][] solution(int[][] nodeinfo) {
int len= nodeinfo.length;
Node[] n = new Node[len];
answer = new int[2][len];
for(int i = 0; i < len; i++)
n[i] = new Node(i+1, nodeinfo[i][0], nodeinfo[i][1], null, null);
Arrays.sort(n, new Comparator<Node>() {
public int compare(Node n1, Node n2) {
if(n1.y == n2.y)
return n1.x-n2.x;
return n2.y-n1.y; //내림차순
}
});
Node root = n[0];
for(int i = 1; i<len; i++) {
Node now = n[i];
tree(root, now);
}
preOrder(root);
idx = 0;
postOrder(root);
return answer;
}
}
'Algorithms > programmers' 카테고리의 다른 글
[Hash] 신고 결과 받기, 베스트앨범 (1) | 2024.03.08 |
---|---|
[Hash] Lv.1 폰켓몬, 완주하지 못한 선수 (0) | 2024.03.04 |
[이분탐색] 징검다리 건너기 (0) | 2024.01.23 |
[이분탐색] 프로그래머스 입국심사 (0) | 2024.01.11 |
[Greedy] 프로그래머스 체육복, 큰 수 만들기, 구명보트, 단속카메라 (1) | 2023.12.28 |