문제 정보

문제 링크
난이도: Lv.3
문제 유형: 자료구조

풀이

접근 방식

접근 자체는 그렇게 어렵지 않았다.

문제에서 대놓고 이진트리, 전위순회, 후위순회를 언급하고 있었고, 제한 사항도 크게 눈여겨볼 게 없어서 구현만 잘 하면 되는 문제라고 생각했다.

대략 다음과 같은 로직으로 문제를 풀었다.

nodeinfo의 정보를 y값을 기준으로 내림차순 정렬
정렬된 정보를 이용해서 이진 트리를 구성
구성한 이진 트리를 전위/후위 순회

구현 과정

0. Node 클래스와 BinaryTree 클래스 구현

먼저 이진트리 구현에 쓸 Node 클래스와 BinaryTree 클래스를 구현했다.

class Node {
	int number;
	int x;
	int y;
	Node left;
	Node right;
 
	public Node (int number, int[] nodeinfo) {
		this.number = number;
		this.x = nodeinfo[0];
		this.y = nodeinfo[1];
	}
}

class BinaryTree {
	Node root;
 
	public BinaryTree (Node root) {
		this.root = root;
	}
 
	// 다른 메서드는 추후 구현
}

1. nodeinfo의 정보를 y값 기준으로 내림차순 정렬

루트 노드를 알아내기 위해 y값을 기준으로 정렬했다.

다만, nodeinfo의 인덱스 + 1이 각 노드 번호기 때문에 nodeinfo를 그대로 정렬하면 안된다.

그래서 먼저 nodeinfo를 반복문으로 돌면서 Node 배열을 만든 후, 그 Node 배열을 내림차순 정렬했다.

버블 정렬을 생각하고 썼는데, 지금 보니 선택 정렬도 아니고 버블 정렬도 아닌 이상한 코드를 썼다.

Node[] nodes = new Node[nodeinfo.length];
 
// Node 배열 생성
for (int i = 0; i < nodeinfo.length; i++) {
	nodes[i] = new Node(i + 1, nodeinfo[i]);
}
 
// Node 배열 내림차순 정렬
for (int i = 0; i < nodes.length; i++) {
	for (int j = i + 1; j < nodes.length; j++) {
		Node tmp;
		if (nodes[i].y < nodes[j].y) {
			tmp = nodes[i];
			nodes[i] = nodes[j];
			nodes[j] = tmp;
		}
	}
}

2. 이진트리 구성

이진트리 구성을 위해 BinaryTree 클래스에 insertNode 메서드를 구현했다.

노드 정보를 y값을 기준으로 내림차순 정렬을 했으므로, 노드 삽입 시 무조건 말단 노드에 자식 노드가 추가되는 경우만 있을 것이다. 그렇기에 x값을 기준으로만 비교했고, 자식 노드가 없을 때 연결해주는 식으로 구현했다.

public void insertNode(Node newNode) {
	Node cur = root;
	while(true) {
		if (cur.x > newNode.x) {
			if (cur.left == null) {
				cur.left = newNode;
				break;
			}
			cur = cur.left;
		} else if (cur.x < newNode.x) {
			if (cur.right == null) {
				cur.right = newNode;
				break;
			}
			cur = cur.right;
		}
	}
}

3. 구성한 이진트리를 전위/후위 순회

BinaryTree 클래스에 전위/후위 순회 메서드를 구현했다.

이 때 전위 순회는 반복적으로, 후위 순회는 재귀적으로 구현했다.
이것도 특별한 이유가 있는 건 아니다. 개인적으로 내가 재귀를 안 좋아해서 반복적인 방법으로 구현하고 싶었는데, 후위 순회를 반복적으로 구현하는 방법이 생각이 나지 않았다.

public List<Integer> preorderTraversal() {
	List<Integer> visit = new ArrayList<>();
	Stack<Node> stack = new Stack<>();
 
	stack.push(root);
	while(!stack.isEmpty()) {
		Node cur = stack.pop();
		
		visit.add(new Integer(cur.number));
		if (cur.right != null)
			stack.push(cur.right);
		if (cur.left != null)
			stack.push(cur.left);
	}
 
	return visit;
}

public List<Integer> postorderTraversal(List<Integer> visit, Node cur) {
	if (cur == null)
		return visit;
 
	postorderTraversal(visit, cur.left);
	postorderTraversal(visit, cur.right);
	visit.add(new Integer(cur.number));
 
	return visit;
}

4. 비즈니스 로직 구현

느낀 점

그렇게 어려울 것 없는 문제였는데, 구현에서 잦은 실수가 있었다.
사용 코드 중에 deprecated된 게 있었다.
- new Integer(int) 대신 Integer.valueOf(int)
- Stack 클래스 대신 Deque 클래스
  - 정확히 말해서 Deque 클래스를 Stack 처럼 쓰라는 것 같다.
코딩 실력의 저하가 뼈저리게 느껴졌다.
코딩 테스트 대비로 문제 푸는 방식을 바꾸려고 하는데, 하다 보니 이전의 문제 푸는 버릇대로 풀었다. 주의해야겠다.

구현 과정 1번 관련

비효율적인 코드를 썼다.
- 시간 복잡도는 $O (n^{2})$ 이겠지만 불필요한 교환이 생긴다.
다른 사람들의 풀이를 보니 Arrays.sort()와 compare()를 재정의해서 쓴 풀이가 많았다. 기억해 둬야겠다.

구현 과정 2번 관련

depth가 3이다.
- ‘객체지향 생활체조 원칙’에 따르면 “한 메서드에서는 한 단계의 들여쓰기만” 하라고 한다. )depth를 최대 2까지는 허용한다는 얘기도 있기는 하지만)
- 어쨌든 최대 depth가 3이라는 점에서 더 나은 코드를 쓸 수 있지 않았을까 하는 아쉬움이 있다.

구현 과정 3번 관련

후위 순회를 반복적으로 구현하는 방법에 대해 다시 공부해야겠다.

전체 코드

import java.util.*;
 
class Solution {
    public int[][] solution(int[][] nodeinfo) {
        int[][] answer = new int[2][];
        Node[] nodes = new Node[nodeinfo.length];
        
        for (int i = 0; i < nodeinfo.length; i++) {
            nodes[i] = new Node(i + 1, nodeinfo[i]);
        }
        
        for(int i = 0; i < nodes.length - 1; i++) {
            for(int j = i + 1; j < nodes.length; j++) {
                Node tmp;
                if (nodes[i].y < nodes[j].y) {
                    tmp = nodes[i];
                    nodes[i] = nodes[j];
                    nodes[j] = tmp;
                } 
            }
        }
        
        Node root = nodes[0];
        BinaryTree binaryTree = new BinaryTree(root);
        
        for(int i = 1; i < nodes.length; i++) {
            binaryTree.insertNode(nodes[i]);
        }
        
        answer[0] = binaryTree.preorderTraversal()
            .stream()
            .mapToInt(Integer::intValue)
            .toArray();
        
        List<Integer> visit = new ArrayList<>();
        answer[1] = binaryTree.postorderTraversal(visit, root)
            .stream()
            .mapToInt(Integer::intValue)
            .toArray();
        
        return answer;
    }
}
 
class Node {
    int number;
    int x;
    int y;
    Node left;
    Node right;
    
    public Node (int number, int[] nodeinfo) {
        this.number = number;
        this.x = nodeinfo[0];
        this.y = nodeinfo[1];
    }
}
 
class BinaryTree {
    Node root;
    
    public BinaryTree (Node root) {
        this.root = root;
    }
    
    public void insertNode(Node newNode) {
        Node cur = root;
        while(true) {
            if (cur.x > newNode.x) {
                if (cur.left == null) {
                    cur.left = newNode;
                    break;
                }
                cur = cur.left;
            } else if (cur.x < newNode.x) {
                if (cur.right == null) {
                    cur.right = newNode;
                    break;
                }
                cur = cur.right;
            }
        }
    }
    
    public List<Integer> preorderTraversal() {
        List<Integer> visit = new ArrayList<>();
        Stack<Node> stack = new Stack<>();
        
        stack.push(root);
        while(!stack.isEmpty()) {
            Node cur = stack.pop();
            
            visit.add(new Integer(cur.number));
            if (cur.right != null)
                stack.push(cur.right);
            if (cur.left != null)
                stack.push(cur.left);
        }
        
        return visit;
    }
    
    public List<Integer> postorderTraversal(List<Integer> visit, Node cur) {
        if (cur == null)
            return visit;
        
        postorderTraversal(visit, cur.left);
        postorderTraversal(visit, cur.right);
        visit.add(new Integer(cur.number));
        
        return visit;
    }
}

EunSung.log

탐색기

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