[SWEA] 1233 사칙연산 유효성 검사

이진트리로 주어진 사칙연산이 유효한지 출력하는 문제다

입력이 조금 복잡하게 들어오는거 빼고는 크게 어렵지는 않은 문제다!

 

문제의 조건을 생각해보면 내가 현재 노드가 숫자일 때, 연산자일 때 나눠보면 된다

 

1. 숫자일 때 => 자식을 가지고 있으면 무조건 false다

2. 연산자라면 => 내 자식 두명을 재귀타고가서 둘다 참이라면 true다

 

코드가 좀 헷갈릴 수 있지만 재귀적으로 생각하면 쉽게 풀 수 있다!

 

소스코드

import java.util.*;
import java.io.*;
 
 
public class Solution {
    public static char[] tree = new char[222];
    public static int n;
    public static void init() {
        for(int i=0;i<n;i++) tree[i]=0;
    }
    public static boolean inner(int x) {
        return (1<=x && x<=n && tree[x]==0);
    }
    public static boolean solve(int x) {
        if(x>n) return false;
        char c = tree[x];
        if('0' <= c && c<='9') {
            if((inner(x*2) && inner(x*2+1)) || (x*2>n) && (x*2+1>n)) return true;
            return false;
        }else return (solve(x*2)&solve(x*2+1));
    }
    public static void main(String[] args) throws FileNotFoundException {
        System.setIn(new FileInputStream("res/input.txt"));
        Scanner sc = new Scanner(System.in);
        
        for(int tc=1;tc<=10;tc++) {
            n = sc.nextInt();
            init();
            String s = sc.nextLine();
            for(int i=1;i<=n;i++) {
                s=sc.nextLine();
                String[] sa = s.split(" ");
                tree[i] = sa[1].charAt(0);
            }
            int ans = (solve(1)==true) ? 1:0;
            System.out.println("#"+tc+" "+ans);
        }
    }
}