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

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV141J8KAIcCFAYD 

SW Expert Academy

설명

사칙연산 “+, -, *, /”와 양의 정수로만 구성된 임의의 이진트리가 주어질 때, 이 식의 유효성을 검사하는 프로그램을 작성하여라.
여기서 말하는 유효성이란, 사칙연산 “+, -, *, /”와 양의 정수로 구성된 임의의 식이 적절한 식인지를 확인하는 것으로,

계산이 가능하다면 “1”, 계산이 불가능할 경우 “0”을 출력한다.
(단, 계산이 가능한지가 아닌 유효성을 검사하는 문제이므로 0으로 나누는 경우는 고려하지 않는다. )

 

 

 

문제의 테스트 케이스를 모두 입력받아서 트리를 구성하고 이것이 유효한 연산 트리인지를 검증해야 할까?

연산이 가능한 트리란 어떤 트리인지를 생각해보자.

 

연산이 가능하려면 무조건 연산자는 루트 노드이고 왼쪽 오른쪽 두 개의 자식 노드를 가져야 한다. (피연산자 2개가 있어야 계산 가능)또한 정수는 단말 노드여야만이 계산이 가능하다. (정수가 루트에 온다? 계산 안됨)테스트 케이스는 1.  해당 정번 번호, 2. 해당 정점의 알파벳, 3. 해당 정점의 왼쪽 자식, 4. 오른쪽 자식의 정점 번호가 차례대로 주어진다.

 

예를 보자.

 

9 * 18 19 → 9번 정점 / 연산자 * / 왼쪽 자식 노드 18 / 오른쪽 자식 노드 19 (O)
10 7 20 21 → 10번 정점 / 숫자 7 / 왼쪽 자식 노드 20 / 오른쪽 자식 노드 21 (X)

 

162 4 → 162번 정점 / 숫자 4 (자식 노드 X) (O)

163 - → 16번 정점 / 연산자 - (X)

 

테스트 코드를 한 줄 한 줄 입력받으면서 연산자일 경우 왼쪽, 오른쪽 자식 노드가 없다면 유효하지 않은 트리

왼쪽 오른쪽 노드가 없는 단말 노드일 경우 정수가 아니라 연산자가 오면 유효하지 않은 트리로 판단하고 유효성을 검증하면 된다.

전체 코드

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

class Solution {
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		int T = 10;

		for(int test_case = 1; test_case <= T; test_case++) {
			int N = Integer.parseInt(br.readLine());
			
			int answer = 1;

			for(int i = 1; i <= N; i++) {
				StringTokenizer st =  new StringTokenizer(br.readLine());
				
				st.nextToken(); // 첫 번째 정점 번호는 패스 
				
				char node = st.nextToken().charAt(0); 
				
				if(st.hasMoreTokens()) { // 단말 노드가 아닐 때 
					if(node >= '0' && node <= '9') { // 연산자여야 함, 숫자 X 
						answer = 0;
					}
				} else { // 단말 노드일 때 
					if(node < '0' || node > '9') { // 숫자여야 함 
						answer = 0;
					}
				}
			}
			sb.append("#" + test_case + " " + answer + "\n");
		}
		System.out.println(sb.toString());
	}
	
}