codingtest

길 찾기 게임

2025-02-06
2분 분량
JAVA프로그래머스

문제 링크

문제 풀이 시간 : 1시간

문제 풀이 :

프로그래머스AI 추천문제를 계속 풀던 중에 정답률이 꽤 낮아보여서 풀게되었는데

문제를 처음 읽었을 때 생각보다 어려운 문제구나 싶었다.

근데 문제를 자세히 읽어보니

그냥 노드 클래스를 만들어서 트리를 만들어주면 되는 간단한 문제였다.

Node 클래스

java
class Node{
    private Integer num, x, y;
    private Node left;
    private Node right;
    
    public Node(int num, int x, int y){
        this.x = x;
        this.y = y;
        this.num = num;
    }
    
    public void setLeft(Node left){
        this.left = left;
    }
    
    public void setRight(Node right){
        this.right = right;
    }
    
    public Integer getX(){
        return x;
    }
    
    public Integer getY(){
        return y;
    }
    
    public Integer getNum(){
        return num;
    }
    
    public Node getRight(){
        return right;
    }
    
    public Node getLeft(){
        return left;
    }
}

노드 객체 생성 후 정렬

java
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]);
}
        
Arrays.sort(nodes,new Comparator<Node>(){//노드를 y내림차순, x오름차순으로 정렬
	@Override
	public int compare(Node a, Node b){
		if(a.getY()==b.getY()){
			return Integer.compare(a.getX(),b.getX());
		}
		return Integer.compare(b.getY(),a.getY());
	}
});

트리 구성

java
Node head = nodes[0]; //루트 노드

for(int i=1;i<nodes.length;i++){
    head = nodes[0];
    while(true){
        if(head.getX()<nodes[i].getX()){ //루트 노드의 x값이 현재 노드의 x값보다 작다면
            if(head.getRight() == null){ //오른쪽 자식이 없다면 오른쪽자식으로 연결
                head.setRight(nodes[i]);
                break;
            }
            head = head.getRight(); //있다면 루트 이동
        }
        else{
            if(head.getLeft() == null){
                head.setLeft(nodes[i]);
                break;
            }
            head = head.getLeft();
        }
    }
}

전,후위 순회

java
public void pre(Node now) {
    if (now == null)
        return;
        
    preorder.add(now.getNum());
    pre(now.getLeft());
    pre(now.getRight());
}
    
public void post(Node now) {
    if (now == null)
        return;
        
    post(now.getLeft());
    post(now.getRight());
    postorder.add(now.getNum());
}

전체 코드

java
import java.util.*;

class Node{
    private Integer num, x, y;
    private Node left;
    private Node right;
    
    public Node(int num, int x, int y){
        this.x = x;
        this.y = y;
        this.num = num;
    }
    
    public void setLeft(Node left){
        this.left = left;
    }
    
    public void setRight(Node right){
        this.right = right;
    }
    
    public Integer getX(){
        return x;
    }
    
    public Integer getY(){
        return y;
    }
    
    public Integer getNum(){
        return num;
    }
    
    public Node getRight(){
        return right;
    }
    
    public Node getLeft(){
        return left;
    }
}

class Solution {
    public ArrayList<Integer> preorder, postorder;
    
    public void pre(Node now){
        if(now==null)
            return;
        
        preorder.add(now.getNum());
        pre(now.getLeft());
        pre(now.getRight());
    }
    
    public void post(Node now){
        if(now == null)
            return;
        
        post(now.getLeft());
        post(now.getRight());
        postorder.add(now.getNum());
    }
    
    
    public int[][] solution(int[][] nodeinfo) {
        int[][] answer = new int[2][nodeinfo.length];
        preorder = new ArrayList<>();
        postorder = new ArrayList<>();
        
        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]);
        }
        
        Arrays.sort(nodes,new Comparator<Node>(){
            @Override
            public int compare(Node a, Node b){
                if(a.getY()==b.getY()){
                    return Integer.compare(a.getX(),b.getX());
                }
                return Integer.compare(b.getY(),a.getY());
            }
        });
        
        Node head = nodes[0];
        
        for(int i=1;i<nodes.length;i++){
            head = nodes[0];
            while(true){
                if(head.getX()<nodes[i].getX()){
                    if(head.getRight() == null){
                        head.setRight(nodes[i]);
                        break;
                    }
                    head = head.getRight();
                }
                else{
                    if(head.getLeft() == null){
                        head.setLeft(nodes[i]);
                        break;
                    }
                    head = head.getLeft();
                }
            }
        }
        
        pre(nodes[0]);
        post(nodes[0]);
        
        for(int i=0;i<nodes.length;i++){
            answer[0][i] = preorder.get(i);
            answer[1][i] = postorder.get(i);
        }
        
        return answer;
    }
}

함께 읽으면 좋은 글

코딩 테스트2026-08-23

택배상자

order 배열은 택배 기사님이 원하는 상자 적재 순서다 기존 컨테이너 벨트는 1번부터 순서대로만 꺼낼 수 있다 보조 벨트는 스택처럼 마지막에 넣은 것부터 꺼낼 수 있다 원하는 순서대로 최대한 실을 수 있는 상자 개수를 구하는 문제다 처음에는 기존 벨트를 실제 리스트로 만들어…

코딩 테스트2026-08-23

롤케이크 자르기

topping 배열은 롤케이크에 일렬로 올라간 토핑 번호다 한 지점을 잘라 두 조각으로 나눴을 때, 양쪽 토핑 종류 수가 같아야 공평하게 나눈 것이다 공평하게 자를 수 있는 방법의 수를 구하는 문제다 처음에는 자르는 위치마다 왼쪽과 오른쪽 배열을 나눠서 각각 서로 다른 토핑…

코딩 테스트2026-08-23

할인 행사

want, number 배열로 정현이가 원하는 제품과 수량을 표현한다 discount 배열은 XYZ 마트가 매일 할인하는 제품 목록이다 연속된 10일 동안 할인 제품 종류와 수량이 want, number와 정확히 일치해야 회원가입할 수 있다 그런 시작일이 총 몇 번 있는지…

코딩 테스트2026-08-23

숫자 변환하기

자연수 x를 y로 바꾸는 데 x+n, x2, x3 세 가지 연산을 쓸 수 있다 x를 y로 바꾸는 최소 연산 횟수를 구하는 문제다 만들 수 없으면 -1을 반환한다 처음에는 x에서 시작해서 세 가지 연산을 재귀적으로 다 시도해보고 y에 도달하는 경로 중 가장 짧은 걸 고르면…

← 서재 목록으로 돌아가기