[JAVA] 사칙연산 유효검사 - Binary Tree

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV141176AIwCFAYD&categoryId=AV141176AIwCFAYD&categoryType=CODE&problemTitle=%EC%82%AC%EC%B9%99%EC%97%B0%EC%82%B0&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy

 

생각과정

- 연산이 가능한 조건 1: 리프 노드는 무조건 숫자여야 한다.

- 연산이 가능한 조건 2: 숫자 자식을 하나라도 가지고 있으면 부모가 반드시 연산자여야 한다.

- 이진 트리를 구현해서 주어진 input값을 다 넣는다.

- 넣은 후 root부터 시작해 재귀로 전위 탐색을 한다.

- 리프 노드일 경우 조건 1을 체크한다.

- 리프 노드가 아닐 경우 조건 2를 체크한다.

 

구현

import java.util.*;
import java.io.*;
public class Solution {
	static String[] tree;
	static int N;
	static boolean isValid;
	static boolean isNumber(String s) {
		if(s.equals("+") || s.equals("-") ||s.equals("*") ||s.equals("/")) {
			return false;
		}else {
			return true;
		}
	}
	
	static void postOrder(int index) {
		if(tree[index] == null) return;
		
		// 리프노드는 무조건 숫자여야 함
		if(index*2 > N || index*2+1 > N) {
			// leaf case 1: 자식 인덱스가 배열을 초과하는 경우
			if(!isNumber(tree[index])) {
				isValid = false;
				//System.out.println("리프 노드가 숫자가 아님");
			}
			return;
		}
		else{
			// leaf case 2: 자식 인덱스의 값이 모두 null인 경우
			if(tree[index*2] == null && tree[index*2+1]==null) {
				if(!isNumber(tree[index])) {
					isValid = false;
					//System.out.println("리프 노드가 숫자가 아님");
				}
				return;
			}
		}
		
		// leaf node가 아닐 경우
		// 숫자 자식을 가지고 있으면 무조건 연산자가 부모여야 함
		if(isNumber(tree[index*2]) || isNumber(tree[index*2+1])) {
			if(isNumber(tree[index])) {
				isValid = false;
				//System.out.println("숫자 자식을 가지고 있으면 무조건 연산자가 부모여야 함");
			}
		}
		
		// 이동
		if(tree[index*2] != null)
			postOrder(index*2);
		if(tree[index*2+1]!=null)
			postOrder(index*2+1);
	}

	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		
		for(int tc=1;tc<=10;tc++) {
			N = Integer.parseInt(in.readLine());
			tree = new String[N+1];
			isValid = true;
			StringTokenizer st;
			for(int i=1;i<=N;i++) {
				st = new StringTokenizer(in.readLine());
				int index = Integer.parseInt(st.nextToken());
				tree[index] = st.nextToken();
				if(index*2 <= N)
					tree[index*2] = st.nextToken();
				if(index*2+1 <= N)
					tree[index*2+1] = st.nextToken();
			}
			
			// 전위 순회하면서 검사하기
			postOrder(1);
			
			if(isValid)
				System.out.println("#" + tc+" 1");
			else
				System.out.println("#" + tc+" 0");
		}
	}

}

 

결과

반복문으로 풀면 실행시간이 덜 걸릴것 같다...!

 

 

이진트리

: 모든 노드들이 2개의 서브트리를 갖는 트리. 자식 노드를 2개까지만 가질 수 있다.

 

- Full Binary Tree

: 리프 노드를 제외한 모든 노드가 자식을 2개 가졌고, 가질 수 있는 최대로 노드를 가진 이진 트리.

 

- Complete Binary Tree

: 이진 트리를 배열로 만들었을 때, 중간에 빈 공간이 없는 트리. 자식 노드를 왼쪽부터 채운다.

 

- Skewed Binary Tree

: 최소 노드 개수를 만족하면서, 한쪽으로만 자식을 가지고 있는 트리.

 

 

이진 트리 순회

- 전위 순회 preorder traversal

: 부모부터 방문하고 자식을 왼쪽, 오른쪽 순으로 방문한다.

// tree: 이진 트리 배열
// index: 현재 노드의 배열 인덱스
static void preOrder(int index){
	if(index >= tree.length) return; // 탐색 종료
    
    // 방문했을 때 수행할 코드
    preOrder(index*2); // 왼쪽 자식 방문
    preOrder(index*2+1); // 오른쪽 자식 방문
}

- 중위 순회 inorder traversal

: 왼쪽 자식부터 방문하고 부모, 오른쪽 자식 순으로 방문한다.

// tree: 이진 트리 배열
// index: 현재 노드의 배열 인덱스
static void inOrder(int index){
	if(index >= tree.length) return; // 탐색 종료
    
    inOrder(index*2); // 왼쪽 자식 방문
    // 방문했을 때 수행할 코드
    inOrder(index*2+1); // 오른쪽 자식 방문
}

- 후위 순회 postorder traversal

: 자식을 왼쪽, 오른쪽 순으로 방문하고 부모를 방문한다.

// tree: 이진 트리 배열
// index: 현재 노드의 배열 인덱스
static void postOrder(int index){
	if(index >= tree.length) return; // 탐색 종료
    
    postOrder(index*2); // 왼쪽 자식 방문
    postOrder(index*2+1); // 오른쪽 자식 방문
    // 방문했을 때 수행할 코드
}