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

문제 출처 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV141176AIwCFAYD&categoryId=AV141176AIwCFAYD&categoryType=CODE&problemTitle=1233&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

SW Expert Academy

 

 

문제

 

 

설명

위 문제에 따라 사칙연산이 유효하려면, 다음과 같은 조건을 만족해야 합니다.

 

1. 노드가 숫자이면, 그 노드는 자식 노드가 없는 리프노드여야만 합니다.

코드에서는 숫자인데 자식 노드가 없는 경우에 바로 answer를 0으로 바꾸고 반복문을 탈출시켰습니다.

 

2. 노드가 연산자이면, 자식 노드가 두개 모두 있어야 합니다.

자식 노드의 조합으로는 '숫자 + 숫자', '연산자 + 연산자', '연산자 + 숫자' 가 가능합니다.

주의할 점은 '숫자 + 연산자' 조합은 불가하다는 것인데, 그 이유는 다음과 같습니다.

위 데이터는 완전 이진트리 형식인데 숫자가 왼쪽 자식으로 올 경우 유효하려면 리프노드여야 하고, 오른쪽 자식인 연산자는 자식이 모두 필요합니다. 이런 모양은 왼쪽부터 빈틈없이 꽉꽉 채워나가는 완전 이진트리 모양이 아니기 때문에 불가능한 것입니다.

저는 코드에서 올바른 위의 세가지 조합을 모두 확인해 보는게 아니라 그냥 '숫자 + 연산자'인지 확인하고 그렇다면 유효하지 않은 것이므로 바로 answer를 0으로 바꾸고 반복문을 탈출하는 식으로 코드를 짰습니다. 

 

 

코드

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

public class SWEA1233_Arithmetic {
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		for(int tc=1; tc<=10; tc++) {
			int N = Integer.parseInt(br.readLine()); //정점의 총 갯수
			
			char[] nodes = new char[N+1];
			int answer=1;
			
			for(int i=1; i<=N; i++) {
				st = new StringTokenizer(br.readLine());
				st.nextToken(); //노드 번호 정보는 필요없으니 한 번 날리고
				nodes[i] = st.nextToken().charAt(0);//노드의 값 저장
			} //입력 완료
			
			for(int i=1; i<=N; i++) {
				int lchild = i*2;
				int rchild = i*2+1;
				
				if(Character.isDigit(nodes[i])) { //만약 노드의 값이 숫자이면 -> 리프노드여야 함
					if(lchild<=N) { //만약 자식이 있다면 유효하지 않음
						answer=0;
						break;
					}
				} else { //만약 노드의 값이 연산자이면
					//1. 리프노드이면 안됨
					//2, 오른쪽 자식이 숫자이고 왼쪽 자식이 연산자이면 안됨
					if(lchild>N) { // 1의 경우
						answer=0; break;
					}
					
					if(Character.isDigit(nodes[lchild]) && !(Character.isDigit(nodes[rchild]))) { //2의 경우
						answer=0; break;
					}
				}
			}
			
			sb.append("#" + tc + " "+answer+"\n");
		}
		System.out.println(sb);
	}
}