[SWEA/Java] 1233. 사칙연산 유효성 검사

[SWEA/Java] 1233. 사칙연산 유효성 검사

SW Expert Academy

---

문제 해석

이 문제는 주어진 이진 트리가 사칙연산을 위한 유효한 표현식을 나타내는지 검사하는 문제이다. 유효성 검사는 노드의 값을 통해 수행된다. 노드에 숫자가 있어야 하는 위치에 연산자가 위치하거나, 연산자가 있어야 하는 위치에 숫자가 위치하는 경우 유효하지 않은 표현식으로 간주한다. 각 테스트 케이스에 대한 유효성 결과를 반환해야 한다.

풀이 과정

프로그램은 총 10개의 테스트 케이스를 수행한다. 각 테스트 케이스에서 노드의 수를 입력받은 후, 각 노드에 대한 정보를 파싱한다. 노드 정보에는 노드 번호, 노드 값, 자식 노드 번호가 포함된다. 노드 값이 연산자인 경우 반드시 자식 노드가 있어야 하며, 숫자인 경우 자식 노드가 있으면 안 된다. 이 규칙을 위반하는 경우 해당 테스트 케이스의 결과는 0(유효하지 않음), 그렇지 않은 경우는 1(유효)로 설정한다.

코드

package edu.ssafy.im.SWEA.D4.No1233;

import java.io.*;
import java.util.StringTokenizer;

public class Solution {
    public static void main(String[] args) throws IOException {
        new Solution().sol();
    }

    private void sol() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        for (int t = 1; t <= 10; t++) {
            int n = Integer.parseInt(br.readLine());
            int ans = 1;  // 유효성 결과 초기값 설정
            for (int i = 1; i <= n; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                st.nextToken();  // 노드 번호는 사용하지 않음
                char op = st.nextToken().charAt(0);  // 노드 값
                
                // 자식 노드가 있는 경우
                if (st.hasMoreTokens()) {
                    // 숫자일 경우, 유효하지 않음
                    if (op >= '0' && op <= '9') {
                        ans = 0;
                    }
                } else {
                    // 연산자일 경우, 유효하지 않음
                    if (op < '0' || op > '9') {
                        ans = 0;
                    }
                }
            }
            sb.append("#").append(t).append(" ").append(ans).append("\n");  // 결과 문자열 생성
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

시간 복잡도 분석

이 문제의 시간 복잡도는 O(N)이다. 각 테스트 케이스마다 모든 노드를 한 번씩만 검사하므로, 노드 수에 비례하는 시간이 소요된다.

느낀점

이 문제를 통해 트리 구조에서의 데이터 유효성 검사 방법을 다루었다. 노드의 값과 자식 노드의 유무를 기반으로 하는 간단한 조건들을 검토함으로써, 복잡한 데이터 구조에서도 효율적으로 정보를 처리할 수 있는 방법을 배울 수 있었다. 이러한 접근 방식은 다양한 문제에 응용될 수 있어 유용하다.