문제 링크

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

풀이

첫 번째 방법

  • 이 문제에서 사칙연산이 유효하지 않는 경우는 다음과 같다.
    1. 피연산자 노드가 자식 노드를 가지고 있는 경우
    2. 연산자 노드가 리프 노드인 경우
    3. 연산자 노드가 자식 노드를 가지고 있어도, 왼쪽 자식이 숫자이고, 오른쪽 자식이 연산자일 경우
      • 왼쪽부터 노드가 추가되어 빈 자리가 없는 완전 이진 트리의 특성 때문이다. 만약 왼쪽 자식이 피연산자이고 오른쪽 자식이 연산자일 경우, 연산자는 자식 노드를 가져야 하는데, 이렇게 되면 완전 이진 트리가 아니게 되므로 모순이다.
  • 사칙연산이 유효하지 않는 조건을 따로 분기하고, 해당되는 경우 result 값을 0으로 설정 후 이후에 읽어오는 모든 라인을 continue로 패스한다. 초기화를 진행한 후에 로직을 수행하는 것이 아니라, 초기화를 진행하면서 로직을 수행하기 때문이다.
소스 코드 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

/**
 * SW Expert Academy 1233번 문제: 사칙연산 유효성 검사
 */
public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int T = 10;
        Set<Character> operand = new HashSet<>(Arrays.asList('+', '-', '*', '/'));
      
        for (int tc = 1; tc <= T; tc++) {
            int n = Integer.parseInt(br.readLine());
            int result = 1;
            
            for (int i = 1; i <= n; i++) {
                // 이미 계산이 불가능하다고 판단된 경우 루프가 끝날 때까지 라인 읽기만 수행
                if (result == 0) {
                    br.readLine();
                    continue;
                }
                
                st = new StringTokenizer(br.readLine());
                st.nextToken();
                char op = st.nextToken().charAt(0);
                
                if (st.hasMoreTokens()) {
                    // 서브 트리의 루트 노드가 피연산자일 경우 0
                    if (!operand.contains(op)) {
                        result = 0;
                        continue;
                    }
                    char left = st.nextToken().charAt(0);
                    
                    // 자식 노드가 하나만 있는 경우 0
                    if (!st.hasMoreTokens()) {
                        result = 0;
                        continue;
                    }
                    char right = st.nextToken().charAt(0);
                    
                    // 왼쪽 자식 노드가 숫자이고, 오른쪽 자식 노드가 연산자이면 0
                    if (!operand.contains(left) && operand.contains(right)) {
                        result = 0;
                    }
                } else {
                    // 리프 노드가 연산자일 경우 0
                    if (operand.contains(op)) {
                        result = 0;
                        continue;
                    }
                }
            }
          
            System.out.println("#" + tc + " " + result);
        }
      
        br.close();
    }
}

두 번째 방법

  • 완전 이진 트리 조건에 의해 첫 번째 노드부터 n/2 노드까지는 연산자이고, 그 이후 노드는 피연산자라는 공식을 사용해서 풀 수도 있다.
  • 단, n이 짝수이면 마지막 노드의 자식 노드가 홀수이므로 n/2 + 1 번째 노드까지 연산자로 취급하도록 한다.
소스 코드 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

/**
 * SW Expert Academy 1233번 문제: 사칙연산 유효성 검사
 */
public class Solution2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int T = 10;
        Set<Character> operand = new HashSet<>(Arrays.asList('+', '-', '*', '/'));
      
        for (int tc = 1; tc <= T; tc++) {
            int n = Integer.parseInt(br.readLine());
            int result = 1;
            
            for (int i = 1; i <= n; i++) {
                // 이미 계산이 불가능하다고 판단된 경우 루프가 끝날 때까지 라인 읽기만 수행
                if (result == 0) {
                    br.readLine();
                    continue;
                }
                
                st = new StringTokenizer(br.readLine());
                st.nextToken();
                char op = st.nextToken().charAt(0);
                
                // n이 짝수이면 마지막 노드의 자식 노드가 홀수이므로
                // n의 짝수 여부에 따라 연산자 개수에 +1 할지 정해야 함
                int opCnt = n/2 + (n%2 == 0 ? 1 : 0);
                
                // 노드 번호가 n/2 이하면 연산자, 그 이후면 피연산자
                if (operand.contains(op) && i > opCnt) result = 0;
                else if (!operand.contains(op) && i <= opCnt) result = 0;
            }
            
            System.out.println("#" + tc + " " + result);
        }
      
        br.close();
    }
}