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);
    }

}
  • はバイナリツリーを簡単に実現すれば解決できる問題である.
  • データは、所与の順序でツリー構成ツリーに挿入され、中位数ソート完了計算式を行う.
  • 以降、計算式が有効かどうかを確認します.演算子の2つの数の間の位置を判断し,解いた.