SW Expert Academy - 1233번(사칙연산 유효성 검사)

문제 출처: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV141176AIwCFAYD&categoryId=AV141176AIwCFAYD&categoryType=CODE&problemTitle=1233&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution {

    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int problemNum = 1;
        BinaryTree binaryTree;
        for (int i = 0; i < 10; i++) {
            int N = Integer.parseInt(reader.readLine());
            binaryTree = new BinaryTree(N);
            int answer = 1;
            while (N-- > 0) {
                StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
                tokenizer.nextToken(); // 정점 숫자
                binaryTree.add(tokenizer.nextToken().charAt(0)); // 트리에 삽입
            }
            char[] temp = binaryTree.inOrder().toCharArray(); // 중위 선회
            for (int j = 1; j < temp.length; j += 2) {
                if (temp[j] >= '0') {
                    answer = 0;
                    break;
                }
            }
            sb.append("#");
            sb.append(problemNum++).append(" ").append(answer).append("\n");
        }
        System.out.println(sb);
    }

}

class BinaryTree {

    private char[] binaryTree;
    private final int size;
    private int lastIndex;
    private StringBuilder sb = new StringBuilder();

    public BinaryTree(int size) {
        this.size = size;
        binaryTree = new char[size + 1];
    }

    public boolean isEmpty() {
        return lastIndex == 0;
    }

    public boolean isFull() {
        return lastIndex == size;
    }

    public void add(char c) {
        if (isFull()) return;

        binaryTree[++lastIndex] = c;
    }

    public String inOrder() {
        if (isEmpty()) return null;
        inOrder(1);
        return sb.toString();
    }

    private void inOrder(int index) {
        if (index > lastIndex) return;

        inOrder(index * 2);
        sb.append(binaryTree[index]);
        inOrder(index * 2 + 1);
    }

}

• 간단히 이진 트리를 구현하여 해결할 수 있는 문제였다.
• 데이터가 주어진 순서대로 트리에 삽입하여 트리를 구성하고, 중위 순회를 하여 계산식을 완성한다.
• 그 후 계산식이 유효한지 확인한다. 두 수 사이에 연산자가 위치하는지를 판단하여 풀이하였다.