[BOJ] 1991번 트리 순회

복기

Python3에서 f-string과 string.join()의 시간 차가 나지 않았다. 하지만 문자열을 구성하는 측면에서는 f-string이 좀 더 편했다. 또, f-string을 이용하니 코드 중복을 상당히 줄일 수 있었다. 세 가지 함수를 사용할 때보다 메모리 사용량과 시간 모두 줄일 수 있었다. 

코드

• C++ 17

#include <iostream> #include <vector>   using namespace std;   using Node = pair<char, char>;   int N; vector<Node> Tree(26);   constexpr size_t GetIndex(char node) {     return node - 'A'; }   void InsertToTree(char root, char left, char right) {     int index = GetIndex(root);     Tree[index] = std::move(make_pair(left, right)); }   void PreOrder(char node) {     int index = GetIndex(node);     auto [left, right] = Tree[index];          cout << node;     if (left != '.')         PreOrder(left);     if (right != '.')         PreOrder(right); }   void InOrder(char node) {     int index = GetIndex(node);     auto [left, right] = Tree[index];       if (left != '.')         InOrder(left);     cout << node;     if (right != '.')         InOrder(right); }   void PostOrder(char node) {     int index = GetIndex(node);     auto [left, right] = Tree[index];       if (left != '.')         PostOrder(left);     if (right != '.')         PostOrder(right);     cout << node; }   int main() {     ios::sync_with_stdio(false);     cin.tie(nullptr);     cout.tie(nullptr);       cin >> N;     for (int i = 0; i < N; ++i)     {         char root, left, right;         cin >> root >> left >> right;         InsertToTree(root, left, right);     }       PreOrder('A');     cout << '\n';     InOrder('A');     cout << '\n';     PostOrder('A'); }

• C# 6.0

using System; using System.Collections.Generic; using System.Text;   namespace Csharp {     class Tree     {         static private StringBuilder stringBuilder = new StringBuilder();                  private class Node         {             public char left = '\0';             public char right = '\0';               public Node(char l, char r)             {                 left = l;                 right = r;             }         }           private Node[] nodes = new Node[26];           public enum EOrder         {             Pre,             In,             Post         }           public void Insert(char root, char left, char right)         {             int index = getIndex(root);             nodes[index] = new Node(left, right);         }           public string Order(EOrder method)         {             stringBuilder.Clear();               switch (method)             {                 case EOrder.Pre:                     preOrderHelper('A');                     break;                 case EOrder.In:                     inOrderHelper('A');                     break;                 case EOrder.Post:                     postOrderHelper('A');                     break;             }               return stringBuilder.ToString();         }           private void preOrderHelper(char node)         {             int index = getIndex(node);             char left = nodes[index].left;             char right = nodes[index].right;               stringBuilder.Append(node);             if (left != '.')                 preOrderHelper(left);             if (right != '.')                 preOrderHelper(right);         }           private void inOrderHelper(char node)         {             int index = getIndex(node);             char left = nodes[index].left;             char right = nodes[index].right;               if (left != '.')                 inOrderHelper(left);             stringBuilder.Append(node);             if (right != '.')                 inOrderHelper(right);         }           private void postOrderHelper(char node)         {             int index = getIndex(node);             char left = nodes[index].left;             char right = nodes[index].right;               if (left != '.')                 postOrderHelper(left);             if (right != '.')                 postOrderHelper(right);             stringBuilder.Append(node);         }           private int getIndex(char node) => node - 'A';     }       class Program     {         static int N;         static Tree tree = new Tree();           static void Main(string[] args)         {             N = Convert.ToInt32(Console.ReadLine());             for (int i = 0; i < N; ++i)             {                 var inputs = Console.ReadLine().Split();                 char root = Convert.ToChar(inputs[0]);                 char left = Convert.ToChar(inputs[1]);                 char right = Convert.ToChar(inputs[2]);                   tree.Insert(root, left, right);             }               Console.WriteLine(tree.Order(Tree.EOrder.Pre));             Console.WriteLine(tree.Order(Tree.EOrder.In));             Console.WriteLine(tree.Order(Tree.EOrder.Post));         }     } }

• Python 3

from sys import stdin from enum import Enum input = stdin.readline   class ETreeOrder(Enum):     Pre = 0     In = 1     Post = 2   N = int(input()) Tree = [ ('.', '.') ] * N       def getIndex(node):     return ord(node) - ord('A')   def order(method, node):     global Tree          idx = getIndex(node)     left, right = Tree[idx]     leftStr, rightStr = '', ''       if left != '.':         leftStr = order(method, left)     if right != '.':         rightStr = order(method, right)       if method == ETreeOrder.Pre:         return f'{node}{leftStr}{rightStr}'     elif method == ETreeOrder.In:         return f'{leftStr}{node}{rightStr}'     else:         return f'{leftStr}{rightStr}{node}'   for _ in range(N):     root, left, right = input().split()     idx = getIndex(root)     Tree[idx] = (left, right)   print(     order(ETreeOrder.Pre, 'A'),     order(ETreeOrder.In, 'A'),     order(ETreeOrder.Post, 'A'),     sep = '\n')