[SWEA 1233] S/W 문제해결 기본] 9일차 - 사칙연산 유효성 검사

문제

• SWEA 1233번
• 문제의 저작권은 SW Expert Academy에 있습니다.

접근방식

이 문제는 수식트리 문제이다. 수식트리의 특징을 떠올려보면 루트노드나 가지노드는 항상 연산자여야하며 2개의 피연산자인 자식 노드를 가져야 한다. 그리고 러프노드는 항상 피연산자여야 한다. 이를 생각해보면 먼저 배열에 담긴 노드를 하나씩 꺼내주면서 루트노드/가지노드 일때와 러프노드 일때의 조건을 걸어준다.

• 루트노드/가지노드인 경우 조건 반드시 자식노드가 2개이어야 하므로 왼쪽 자식 노드인 2 * i번과 오른쪽 자식 노드인 2 * i + 1번이 전체 노드 수인 N이하여야 한다. 이를 만족할 때 노드값이 숫자일 경우(아스키코드로 ‘0’(32) ~ 9’41’일 경우)에 ans = 0으로 변경하고 탐색을 종료한다.
• 러프노드인 경우 조건
  왼쪽과 오른쪽 자식노드가 없어야 하므로 왼쪽 자식 노드인 2 * i번과 오른쪽 자식 노드인 2 * i + 1번이 전체 노드 수인 N보다 커야한다. 이를 만족할 때 노드 값이 피연산자인 ‘+’,’-‘,’x’,’/’ 중 하나일 경우에 ans = 0으로 변경하고 탐색을 종료한다.

추가로 의문이 드는 부분은 노드 입력값에 대한 범위가 정확히 주어지지 않았다는 점이다. 나는 풀 때 숫자 범위를 0~9로 주어도 tc통과가 되었지만 입력값에 대한 정확한 범위 지정이 필요할 것 같다.

코드

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

//수식트리 문제
public class Swea_1233 {
	static char[] tree;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		for (int tc = 1; tc <= 10; tc++) {
			int N = Integer.parseInt(br.readLine()); // 트리 크기
			tree = new char[N + 1];

			// 트리배열에 넣고
			for (int i = 1; i <= N; i++) {
				String[] line = br.readLine().split(" ");
				tree[i] = line[1].charAt(0);
			}

			int ans = 1;
			// 하나씩 탐색하면서 유효성 검사
			for (int i = 1; i <= N; i++) {
				// 1. 루트/가지트리: 왼쪽과 오른쪽 자식 노드가 있는데 현재 노드가 피연산자라면
				// 연산자는 밑에 피연산자는 항상 2개(왼,오 자식 모두 존재)
				if ((i * 2 <= N && i * 2 + 1 <= N) && (tree[i] >= '0' && tree[i] <= '9')) {
					ans = 0;
					break;
				}
				
				// 2. 리프노드: 왼쪽과 오른쪽 자식노드가 없는데 현재 노드가 연산자라면
				if((i * 2 > N && i * 2 > N) && (tree[i] == '+' || tree[i] == '-' || tree[i] == '*' || tree[i] == 'x')) {
					ans = 0;
					break;
				}
			}
			System.out.println("#"+tc+" "+ans);
		}
	}
}