SWExpertAcademy 1233번-사칙연산 유효성 검사(JAVA)

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

SW Expert Academy

 

사칙연산으로 구성되어 있는 식은 이진 트리로 표현할 수 있다.

아래는 식 “(8/2)*(6-4)”을 이진 트리로 표현한 것이다.

임의의 정점에 연산자가 있으면 해당 연산자의 왼쪽 서브 트리의 결과와 오른쪽 서브 트리의 결과를 사용해서 해당 연산자를 적용한다.

 

 
사칙연산 “+, -, *, /”와 양의 정수로만 구성된 임의의 이진 트리가 주어질 때, 이 식의 유효성을 검사하는 프로그램을 작성하여라.

여기서 말하는 유효성이란, 사칙연산 “+, -, *, /”와 양의 정수로 구성된 임의의 식이 적절한 식인지를 확인하는 것으로, 계산이 가능하다면 “1”, 계산이 불가능할 경우 “0”을 출력한다.

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

       

                         

 

            
[연산이 가능한 경우]                                                  [연산이 불가능한 경우]

[제약 사항]

총 10개의 테스트 케이스가 주어진다.

총 노드의 개수는 200개를 넘어가지 않는다.

트리는 완전 이진 트리 형식으로 주어지며, 노드당 하나의 연산자 또는 숫자만 저장할 수 있다.

노드는 아래 그림과 같은 숫자 번호대로 주어진다.
 

 
[입력]

각 테스트 케이스의 첫 줄에는 각 케이스의 트리가 갖는 정점의 총 수 N(1≤N≤200)이 주어진다.

그 다음 N줄에 걸쳐 각각의 정점 정보가 주어진다.

해당 정점에 대한 정보는 해당 정점의 알파벳, 해당 정점의 왼쪽 자식, 오른쪽 자식의 정점번호가 차례대로 주어진다.

정점 번호는 1부터 N까지의 정수로 구분된다. 입력에서 정점 번호를 매기는 규칙은 위와 같으며, 루트 정점의 번호는 반드시 1이다.

입력에서 이웃한 숫자 또는 연산자, 자식 정점의 번호는 모두 공백으로 구분된다.

위의 예시에서, 숫자 8이 4번 정점에 해당하면 “4 8”으로 주어지고, 연산자 ‘/’가 2번 정점에 해당하면 두 자식이 각각 숫자 ‘8’인 4번 정점과 숫자 ‘2’인 5번 정점이므로 “2 / 4 5”로 주어진다.

총 10개의 테스트 케이스가 주어진다.

[출력]

#부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 테스트 케이스의 정답을 출력한다.

 

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

public class Solution {
	static int result;

	static class Node {
		char value;
		Node leftChild;
		Node rightChild;

		public Node(char value) {
			this.value = value;
			this.leftChild = null;
			this.rightChild = null;
		}
	}

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

		int T = 10;
		for (int t = 1; t <= T; t++) {
			int N = Integer.parseInt(br.readLine());
			result = 1;
			sb.append("#" + t + " ");
			LinkedList<Node> tree = new LinkedList<Node>();
			tree.add(null);
			for (int n = 1; n <= N; n++) {
				String str = br.readLine();
				st = new StringTokenizer(str, " ");
				st.nextToken();
				tree.add(new Node(st.nextToken().charAt(0)));
			}
			for (int n = 2; n <= N; n++) {
				if (n % 2 == 0)
					tree.get(n / 2).leftChild = tree.get(n);
				else
					tree.get(n / 2).rightChild = tree.get(n);
			}
			postorderTree(tree.get(1));
			sb.append(result + "\n");
		}
		System.out.println(sb);
	}

	public static void postorderTree(Node root) {
		if (root.leftChild != null)
			postorderTree(root.leftChild);
		if (root.rightChild != null)
			postorderTree(root.rightChild);
		if (root.leftChild != null && root.rightChild != null) {
			if (!"+-*/".contains(root.leftChild.value + "") && !"+-*/".contains(root.rightChild.value + "")) {
				root.value = '1';
			} else {
				result = 0;
				return;
			}
		}else return;
	}
}

 

Node 클래스

- char value(노드에 들어있는 값)

- Node leftChild (왼쪽 자식 노드)

- Node rightChild (오른쪽 자식 노드)

- public Node(char value) (value값을 업데이트, 자식 노드들을 null로 초기화)

 

Node타입의 LinkedList를 만들어 tree를 관리했습니다.

- LinkedList<Node> tree = new LinkedList<Node>();

 

트리 입력값 중 두번째 값만 사용하기 때문에 입력문을 다음과 같이 작성했습니다.

-

for (int n = 1; n <= N; n++) {
String str = br.readLine();
st = new StringTokenizer(str, " ");
st.nextToken(); //첫번째 값은 버리는 값
tree.add(new Node(st.nextToken().charAt(0))); //두번째 값까지만 받고 다음 for문으로 넘어감
}

 

자식노드를 연결해주는 반복문입니다

-

for (int n = 2; n <= N; n++) {
if (n % 2 == 0)
tree.get(n / 2).leftChild = tree.get(n);
else
tree.get(n / 2).rightChild = tree.get(n);
}

 

자식노드까지 연결해준 뒤 연산의 유효함을 확인하기 위해 후위 순회 재귀함수를 호출했습니다.

- postorderTree(tree.get(1));

후위순회 함수

후위 순회의 탐색 순서는 오른쪽 그림과 같으므로 왼쪽 자식노드 먼저 탐색하고, 이후 오른쪽 자식 노드 탐색, 마지막으로 부모노드 탐색 순으로 작성했습니다.

- 왼쪽 자식노드가 null이 아니면 왼쪽 자식 노드로 진행

- 왼쪽 탐색 종료 후, 오른쪽 자식노드가 null이 아니면 오른쪽 자식 노드로 진행

- 자식노드 탐색 종료 후 부모 노드 진행

  2개의 자식노드 모두가 null이 아닐 때,

  2개의 자식 노드 모두 연산자가 아니라 숫자이면 연산이 유효하므로 연산자였던 부모노드를 숫자로 변경.

  2개의 자식 노드 중 하나라도 숫자가 아니라면 유효함을 나타내는 static 변수 result를 0으로 변경하고 return

public static void postorderTree(Node root) {
if (root.leftChild != null)
postorderTree(root.leftChild);
if (root.rightChild != null)
postorderTree(root.rightChild);
if (root.leftChild != null && root.rightChild != null) {
if (!"+-*/".contains(root.leftChild.value + "") && !"+-*/".contains(root.rightChild.value + "")) {
root.value = '1';
} else {
result = 0;
return;
}
}else return;
}

 

후위 순회로 유효 연산을 검사하는 로직을 이해를 돕기 위한 그림입니다.

다음 세트가 이전 세트와 동일한 형식이므로 재귀함수로 반복작업을 수행시킨 풀이입니다.