www.acmicpc.net/problem/1991

 

1991번: 트리 순회

첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자

www.acmicpc.net

트리 순회의 간단한 문제입니다.

 

input으로 주어지는 노드는 A~Z까지 26개이므로 숫자로 변환하여 인덱스화 하였습니다.

list배열에 각 노드의 왼쪽자식을 [0]에, 오른쪽 자식을 [1]에 저장하여 순회하였습니다.

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
package BOJ.data_structure;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Boj1991 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuffer sb = new StringBuffer();
    static int list[][] = new int[27][2];
    static int N;
 
    static void preorder(int v) {
        sb.append((char) (v + 'A'));
        if (list[v][0] != -1)
            preorder(list[v][0]);
        if (list[v][1] != -1)
            preorder(list[v][1]);
    }
 
    static void inorder(int v) {
        if (list[v][0] != -1)
            inorder(list[v][0]);
        sb.append((char) (v + 'A'));
        if (list[v][1] != -1)
            inorder(list[v][1]);
    }
 
    static void postorder(int v) {
        if (list[v][0] != -1)
            postorder(list[v][0]);
        if (list[v][1] != -1)
            postorder(list[v][1]);
        sb.append((char) (v + 'A'));
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            char x = st.nextToken().charAt(0);
            char l = st.nextToken().charAt(0);
            char r = st.nextToken().charAt(0);
 
            if (l == '.')
                list[x - 'A'][0] = -1;
            else
                list[x - 'A'][0] = l - 'A';
 
            if (r == '.')
                list[x - 'A'][1] = -1;
            else
                list[x - 'A'][1] = r - 'A';
 
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        preorder(0);
        sb.append("\n");
        inorder(0);
        sb.append("\n");
        postorder(0);
        sb.append("\n");
        System.out.println(sb.toString());
    }
}
cs

'algorithm > data-structure' 카테고리의 다른 글

boj 4358 생태학  (0) 2021.01.25
boj 5639 이진 검색 트리  (0) 2021.01.24
boj 11003 최솟값 찾기  (0) 2021.01.22
boj 2517 달리기  (0) 2021.01.22
boj 3425 고스택  (0) 2021.01.22

 

https://www.acmicpc.net/problem/3425

 

3425번: 고스택

각각의 입력값에 대해서, 해당하는 프로그램을 수행한 뒤, 출력값을 출력하면 된다. 출력값이란 스택에 저장되어 있는 숫자이다. 만약, 프로그램 에러가 발생하거나, 모든 수행이 종료됐을 때

www.acmicpc.net

[이 문제에서 수행하는 연산]

NUM X : X를 스택의 가장 위에 저장

POP : 스택 가장 위의 숫자를 제거

INV : 첫 번째 수의 부호를 변경

DUP : 첫 번째 수를 스택의 가장위에 한번 더 저장

SWP : 첫 번째 수와 두 번째 수의 위치를 변경

ADD : 첫 번째 수 + 두 번째 수

SUB : 두 번째 수 - 첫 번째 수

MUL : 첫 번째 수 * 두 번째 수

DIV : 두 번째 수 / 첫 번째 수

MOD : 두 번째 수 % 첫 번째 수

 

위의 연산들이 랜덤으로 주어지고, 입력값 V가 주어질 때마다 이 연산들을 수행한 결과를 출력합니다.

 

문제에서 요구하는 조건을 종합하면

1. 숫자가 부족해서 연산수행을 하지 못할 때

2. DIV, MOD 연산 시 0으로 나눴을 때

3. 연산 결과의 절댓값이 109 보다 클 때

4. 모든 연산이 종료되었을 때 스택에 저장되어 있는 숫자가 1개가 아닐 때

라고 할 수 있고, 그럼 출력값의 조건으로는

 

모든 연산이 종료되었을 때 스택에 저장되어 있는 숫자가 1개이고 절댓값이 109보다 작거나 같을 때 입니다.

 

나머지는 연산이 요구하는대로 계산해 주시면 됩니다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Stack;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br;
    static StringTokenizer st;
    static String type;
    static ArrayList<String[]> list = new ArrayList<>();
    static Stack<long[]> stack = new Stack<>();
    static long N;
    static final long INF = 1000000000;
 
    static boolean func() {
        stack.push(new long[] {N});
        for (String[] arr : list) {
            if ("NUM".equals(arr[0])) {
                stack.push(new long[] {Long.parseLong(arr[1])});
            } else if ("POP".equals(arr[0])) {
                if (stack.isEmpty())
                    return false;
                stack.pop();
            } else if ("INV".equals(arr[0])) {
                if (stack.isEmpty())
                    return false;
                long a = stack.peek()[0];
                stack.pop();
                stack.push(new long[] {-a});
            } else if ("DUP".equals(arr[0])) {
                if (stack.isEmpty())
                    return false;
                stack.push(stack.peek());
            } else if ("SWP".equals(arr[0])) {
                if (stack.size() < 2)
                    return false;
                long num1 = stack.peek()[0];
                stack.pop();
                long num2 = stack.peek()[0];
                stack.pop();
                stack.push(new long[] {num1});
                stack.push(new long[] {num2});
            } else if ("ADD".equals(arr[0])) {
                if (stack.size() < 2)
                    return false;
                long num1 = stack.peek()[0];
                stack.pop();
                long num2 = stack.peek()[0];
                stack.pop();
                stack.push(new long[] {num1+num2});
            } else if ("SUB".equals(arr[0])) {
                if (stack.size() < 2)
                    return false;
                long num1 = stack.peek()[0];
                stack.pop();
                long num2 = stack.peek()[0];
                stack.pop();
                stack.push(new long[] {num2-num1});
            } else if ("MUL".equals(arr[0])) {
                if (stack.size() < 2)
                    return false;
                long num1 = stack.peek()[0];
                stack.pop();
                long num2 = stack.peek()[0];
                stack.pop();
                stack.push(new long[] {num1*num2});
            } else if ("DIV".equals(arr[0])) {
                if (stack.size() < 2)
                    return false;
                long num1 = stack.peek()[0];
                stack.pop();
                if (num1 == 0)
                    return false;
                long num2 = stack.peek()[0];
                stack.pop();
                stack.push(new long[] {num2/num1});
            } else if ("MOD".equals(arr[0])) {
                if (stack.size() < 2)
                    return false;
                long num1 = stack.peek()[0];
                stack.pop();
                if (num1 == 0)
                    return false;
                long num2 = stack.peek()[0];
                stack.pop();
                stack.push(new long[] {num2%num1});
            }
        }
        
        return true;
    }
 
    static void numinput() throws Exception {
        boolean chk = false;
        st = new StringTokenizer(br.readLine());
 
        int tc = Integer.parseInt(st.nextToken());
        while (tc-- > 0) {
            st = new StringTokenizer(br.readLine());
 
            N = Long.parseLong(st.nextToken());
            chk = func();
            if (!chk || stack.size() != 1) {
                System.out.println("ERROR");
            } else {
                if(Math.abs(stack.peek()[0])>INF)
                    System.out.println("ERROR");    
                else
                    System.out.println(stack.peek()[0]);
            }
 
            while (!stack.isEmpty())
                stack.pop();
        }
        
        while(!list.isEmpty())
            list.remove(0);
    }
 
    static void typeinput() throws Exception {
        while (true) {
            st = new StringTokenizer(br.readLine());
 
            type = st.nextToken();
            if ("NUM".equals(type)) {
                String num = st.nextToken();
                list.add(new String[] { type, num });
            } else if ("END".equals(type) || "QUIT".equals(type)) {
                break;
            } else {
                list.add(new String[] { type });
            }
        }
    }
 
    public static void main(String[] args) throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        while (true) {
            typeinput();
            if ("QUIT".equals(type))
                break;
            numinput();
            st = new StringTokenizer(br.readLine());
            System.out.println();
        }
    }
}
 
 cs

'algorithm > data-structure' 카테고리의 다른 글

boj 4358 생태학  (0) 2021.01.25
boj 5639 이진 검색 트리  (0) 2021.01.24
boj 1991 트리 순회  (0) 2021.01.22
boj 11003 최솟값 찾기  (0) 2021.01.22
boj 2517 달리기  (0) 2021.01.22

+ Recent posts

티스토리툴바