[알고리즘] 1233. 사칙연산 유효성 검사

0. 문제

 

SW Expert Academy

 

---

1. 문제 이해

 

1. 트리

 

---

2. 제출

 

방법 1

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

public class SWEA1233 {

    static String[] opers = {"+", "-", "*", "/"};
    static int level, firstLeaf, lastLeaf;
    static int N;
    static BufferedReader br;
    static StringTokenizer st;
    public static void main(String[] args) throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb = new StringBuffer();

        for(int tc=1; tc<=10; tc++) {
//        for(int tc=1; tc<=1; tc++) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());

            level = (int)(Math.log(N)/Math.log(2));
            firstLeaf = (int)Math.pow(2, level) - ((int)Math.pow(2, (level+1))-1-N)/2;
            lastLeaf = N;
            //System.out.println(level+" "+firstLeaf+" "+lastLeaf);

            boolean flag1 = checkOper(tc);
            boolean flag2 = checkLeaf(tc);
            sb.append("#").append(tc).append(" ").append((flag1 && flag2) ? 1 : 0).append("\n");
        }
        System.out.println(sb.toString());
        br.close();
    }

    static boolean checkOper(int tc) throws Exception {
        boolean flag = true;
        label : for(int i=1; i<firstLeaf; i++) { // 루트, 중간 노드
            String[] arr = br.readLine().split(" ");

            // 연산자인지 확인
            for(String oper : opers) {
                if(arr[1].equals(oper)) {
                    continue label;
                }
            }
            flag = false;
            //System.out.println(tc+"oper i :"+i + " node : " + arr[0]+" : "+ arr[1]);
        }
        return flag; // 모든 검사 통과
    }

    static boolean checkLeaf(int tc) throws Exception {
        boolean flag = true;
        label : for(int i=firstLeaf; i<=lastLeaf; i++) { // 단말 노드
            String[] arr = br.readLine().split(" ");

            // 숫자인지 확인
            if((arr[1].charAt(0) >= '0') && (arr[1].charAt(0) <= '9')) { 
                continue label;
            }
            flag = false;
            //System.out.println(tc+" leaf i :"+i + " node : " + arr[0]+" : "+ arr[1]);
        }
        return flag; // 모든 검사 통과
    }
}

• firstLeaf = (int)Math.pow(2, level) - ((int)Math.pow(2, (level+1))-1-N)/2;
  : 첫번째 단말 노드의 인덱스를 계산한다.
• boolean flag1 = checkOper(tc); : 루트, 중간 노드는 모두 연산자인지 확인하다.
• boolean flag2 = checkLeaf(tc); : 단말 노드가 모두 숫자인지 확인한다.

 

---

방법 2

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class SWEA1233_2 {

    static int N;
    static List<Node> list;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuffer sb = new StringBuffer();

        for(int tc=1; tc<=10; tc++) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            list = new ArrayList<>(N);
            list.add(null); // 0번째

            for(int i=1; i<=N; i++) {
                String[] input = br.readLine().split(" ");
                Node newNode = new Node(input[1], i*2, i*2+1);
                list.add(newNode);
            }
            boolean flag = check();
            sb.append("#").append(tc).append(" ").append(flag ? 1 : 0).append("\n");
        }

        System.out.println(sb);
        br.close();
    }

    static boolean check() {
        for(int i=1; i<=N; i++) {
            Node node = list.get(i);

            // 단말노드
            if((node.left>N)&&(node.right>N)) {
                boolean isNum = '0' <= node.data.charAt(0) && node.data.charAt(0) <= '9';
                if(!isNum) return false;
            }
            // 비단말노드
            else {
                boolean isOper = false;
                isOper = node.data.charAt(0) == '+' || node.data.charAt(0) == '-' || node.data.charAt(0) == '*' || node.data.charAt(0) == '/'; 
                if(!isOper) return false;
            }
        }
        return true;
    }

    static class Node {
        String data;
        int left;
        int right;

        Node(String data, int left, int right){
            this.data = data;
            this.left = left;
            this.right = right;
        }

    }

}

• if((node.left>N)&&(node.right>N)) { : 단말 노드인지 쉽게 확인하는 방법.

 

---