문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/42892
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
💡 풀이
주어진 데이터를 토대로 이진 트리를 만들고, 전위 순회, 후위 순회를 구현하면 되는 자료구조 문제입니다.
데이터 처리
우선, 각 노드를 저장할 클래스를 만들어 줍니다.
Node
class Node {
int index;
int x, y;
Node left, right;
Node(int index, int x, int y) {
this.index = index;
this.x = x;
this.y = y;
left = null;
right = null;
}
}
좌표로 주어지는 노드를 순서에 알맞게 처리하기 위해 우선순위 큐를 사용했습니다. 우선순위 큐의 정렬 조건은 다음과 같습니다.
Y 좌표의 값이 큰 순서대로 정렬. 만약 Y 좌표 값이 같다면, X 좌표 값이 작은 순서대로 정렬
우선순위 큐
PriorityQueue<Node> pq = new PriorityQueue<>((o1, o2) -> {
if(o1.y == o2.y) {
return o1.x - o2.x;
}
return o2.y - o1.y;
});
이진트리 만들기
데이터를 삽입한 우선순위 큐를 토대로 `insertNode` 메서드를 만들어, 이진트리를 만들어 줍니다.
root = pq.poll();
while(!pq.isEmpty()) {
insertNode(root, pq.poll());
}
...
void insertNode(Node parent, Node child) {
if(child.x < parent.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);
}
}
}
트리 탐색
만들어진 이진 트리를 토대로, 전위 순회와 후위 순회를 구현해주면 문제가 해결됩니다.
전위순회
void preOrder(Node cur) {
if(cur != null) {
answer[0][index++] = cur.index;
preOrder(cur.left);
preOrder(cur.right);
}
}
후위순회
void postOrder(Node cur) {
if(cur != null) {
postOrder(cur.left);
postOrder(cur.right);
answer[1][index++] = cur.index;
}
}
전체 코드
전체적인 코드는 아래와 같습니다.
import java.util.*;
class Solution {
PriorityQueue<Node> pq;
Node root;
int[][] answer;
int index;
public int[][] solution(int[][] nodeinfo) {
answer = new int[2][nodeinfo.length];
pq = new PriorityQueue<>((o1, o2) -> {
if(o1.y == o2.y) {
return o1.x - o2.x;
}
return o2.y - o1.y;
});
for(int i = 0; i < nodeinfo.length; i++) {
Node node = new Node(i + 1, nodeinfo[i][0], nodeinfo[i][1]);
pq.offer(node);
}
root = pq.poll();
while(!pq.isEmpty()) {
insertNode(root, pq.poll());
}
index = 0;
preOrder(root);
index = 0;
postOrder(root);
return answer;
}
void insertNode(Node parent, Node child) {
if(child.x < parent.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);
}
}
}
void preOrder(Node cur) {
if(cur != null) {
answer[0][index++] = cur.index;
preOrder(cur.left);
preOrder(cur.right);
}
}
void postOrder(Node cur) {
if(cur != null) {
postOrder(cur.left);
postOrder(cur.right);
answer[1][index++] = cur.index;
}
}
class Node {
int index;
int x, y;
Node left, right;
Node(int index, int x, int y) {
this.index = index;
this.x = x;
this.y = y;
left = null;
right = null;
}
}
}
'알고리즘 > 프로그래머스' 카테고리의 다른 글
[Programmers] Level 3 : 셔틀버스 (0) | 2024.09.22 |
---|---|
[Programmers] Level 3 : 단어 변환(Java) (0) | 2024.04.02 |
[프로그래머스] Level 2 : 순위 검색(Java) (0) | 2023.10.31 |
[프로그래머스] Level 2 : 이모티콘 할인행사(Java) (0) | 2023.10.25 |
[프로그래머스] Level 2 : N-Queen(Java) (1) | 2023.10.23 |