• TOC {:toc}

이 글은 백준 온라인 저지의 1991번 문제를 풀이한 것을 모아놓은 글입니다.

일종의 연습 기록이며 제가 정답을 받은 코드와 참고할만한 다른 코드를 같이 기록합니다. 필요한 경우 코드에 대한 해설을 기록합니다만 코드는 통과했어도 해설은 틀릴 수 있기 때문에 가볍게 참고해주시길 부탁드립니다. 피드백은 편하신 방법으로 자유롭게 주시면 감사하겠습니다.

2021.05.20 (Python)

메모리 시간 코드 길이
29200 KB 68 ms 762 B
단계 시작 시각 끝난 시각 걸린 시간
문제 이해 11:28:58 11:32:02
풀이 생각 11:32:03 11:33:55
코딩 1 전위 11:40:32 12:40:01
코딩 2 후위 14:02:49 14:22:20
코딩 3 중위 14:22:28 14:48:09 
# 전위 순회
def PRE(N):
    if not len([x for x in T[N] if x != "."]):
        print(N, end="")
        return
    print(N, end="")
    for x in T[N]:
        if x != ".":
            PRE(x)

# 중위 순회
def IN(N):
    if not len([x for x in T[N] if x != "."]):
        print(N, end="")
        return
    for x in T[N]:
        if x != ".":
            IN(x)
        if x == T[N][-1]:
            break
        print(N, end="")

# 후위 순회
def POST(N):
    if not len([x for x in T[N] if x != "."]):
        print(N, end="")
        return
    for x in T[N]:
        if x != ".":
            POST(x)
    print(N, end="")


T = {}
R = ""
for i in range(int(input())):
    N = list(input().split())
    if i == 0:
        R = N[0]
    T[N[0]] = N[1:]

PRE(R)
print()
IN(R)
print()
POST(R)
print()

아이디어 & 풀이

하위 노드에 대해서 동일한 함수를 반복하되 순회 방식에 따라 하위 노드 접근 전, 중, 후에 해당 노드를 출력한다.

T[N]의 원소에 대해 .이 아닐 경우 원소를 반환했을 때 원소가 존재하지 않으면 종결한다 (종결조건, leaf node).

디버그

  • 처음에 조건식을 편하게 쓰기 위해서 replace()를 이용해서 .을 False로 바꾸려고 했는데 바꾸는 대상도 str 형태여야 해서 못 했다.
  • 그냥 .과 직접 비교함.

피드백

  • 자식 노드가 두 개밖에 없으니까 반복문을 사용하는 것보다 그냥 인덱스 0, 1로 직접 접근하는 게 더 깔끔하다.
  • A가 항상 루트 노드라는 조건이 있어서 루트를 따로 받지 않아도 됐었다.
  • . 조건 검사를 비효율적으로 많이 했다. .에 상관없이 일단 함수를 호출한 뒤 종결 조건으로 .인지만 검사하면 됐었다.

2022.04.07 (JS)

메모리 시간 코드 길이
9356 KB 124 ms 919 B
단계 시작 시각 끝난 시각 걸린 시간
문제 이해 15:54:26 15:55:03
풀이 생각 15:55:05 15:59:23
코딩 15:59:24 16:13:43 
const fs = require("fs");
const input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");

function main() {
    function preorder(n) {
        if (n === ".") return;

        preStr += n;
        node[n].forEach((child) => preorder(child));
    }

    function inorder(n) {
        if (n === ".") return;

        const child = node[n];

        inorder(child[0]);
        inStr += n;
        inorder(child[1]);
    }

    function postorder(n) {
        if (n === ".") return;

        node[n].forEach((child) => postorder(child));
        postStr += n;
    }

    let preStr = "";
    let inStr = "";
    let postStr = "";

    preorder("A");
    inorder("A");
    postorder("A");

    console.log(preStr);
    console.log(inStr);
    console.log(postStr);
}

const [N, ...lines] = input;
const node = {};
lines.forEach((line) => {
    const [p, l, r] = line.split(" ");
    node[p] = [l, r];
});

main();

참고 답안 1

# 풀이 1-1
import sys

def preorder(node):
    if node == ".":
        return
    print(node, end="")
    preorder(tree[node][0])
    preorder(tree[node][1])

def inorder(node):
    if node == ".":
        return
    inorder(tree[node][0])
    print(node, end="")
    inorder(tree[node][1])

def postorder(node):
    if node == ".":
        return
    postorder(tree[node][0])
    postorder(tree[node][1])
    print(node, end="")

tree = {}
for _ in range(int(input())):
    root, left, right = input().split()
    tree[root] = (left, right)

preorder("A")
print()
inorder("A")
print()
postorder("A")

# 풀이 1-2
import sys

def preorder(node):
    left, right = tree[node]
    print(node, end="")
    if left != ".":
        preorder(left)
    if right != ".":
        preorder(right)

def inorder(node):
    left, right = tree[node]
    if left != ".":
        inorder(left)
    print(node, end="")
    if right != ".":
        inorder(right)

def postorder(node):
    left, right = tree[node]
    if left != ".":
        postorder(left)
    if right != ".":
        postorder(right)
    print(node, end="")


input()
tree = [line.split() for line in sys.stdin.read().splitlines()]
tree = {root: (left, right) for root, left, right in tree}

for order in (preorder, inorder, postorder):
    order("A")
    print()

# 풀이 1-3
def preorder(node):
    global tree

    if node in tree:
        print(node, end="")
        preorder(tree[node][0])
        preorder(tree[node][1])

def inorder(node):
    global tree

    if node in tree:
        inorder(tree[node][0])
        print(node, end="")
        inorder(tree[node][1])

def postorder(node):
    global tree

    if node in tree:
        postorder(tree[node][0])
        postorder(tree[node][1])
        print(node, end="")


tree = {}
for _ in range(int(input())):
    root, left, right = input().split()
    tree[root] = [left, right]

preorder("A")
print()
inorder("A")
print()
postorder("A")

아이디어 & 풀이

기본적인 과정은 위의 답과 비슷하다.

  • 함수 여러 개를 유사하게 실행할 때, 함수명들을 리스트나 튜플로 만들어 순회하면 된다 (풀이 1-2).
  • tree의 key에는 .이 포함되어있지 않기 때문에 .이 아닌 것을 판별하기 위해 if node in tree를 사용할 수 있다 (풀이 1-3).

global 키워드는 함수 안에서 전역변수를 변경하기 위해서 사용한다.

참고 답안 2

const fs = require("fs");
const input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");

function preorder(n) {
    if (n === ".") return "";

    const [childL, childR] = node[n];
    return n + preorder(childL) + preorder(childR);
}

function inorder(n) {
    if (n === ".") return "";

    const [childL, childR] = node[n];
    return inorder(childL) + n + inorder(childR);
}

function postorder(n) {
    if (n === ".") return "";

    const [childL, childR] = node[n];
    return postorder(childL) + postorder(childR) + n;
}

function main() {
    console.log(preorder("A"));
    console.log(inorder("A"));
    console.log(postorder("A"));
}

const [N, ...lines] = input;
const node = {};
lines.forEach((line) => {
    const [p, l, r] = line.split(" ");
    node[p] = [l, r];
});

main();