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

1. 문제 

SW Expert Academy

---

2. 풀이

이 문제는 두 가지 방식을 이용해서 풀었다.

1. 입력받을 때, 자식이 있는 노드라면 무조건 연산자여야한다. 따라서 그걸 체크 하는 방법
2. 모두 입력받은 뒤, 자식이 있는 노드인데 해당 노드가 연산자가 아니거나 자식노드 중 하나라도 유효한 노드가 아닐 때를 체크하는 방법

둘 다 같은 말인데 2번이 좀 더 복잡하고 길게 푼 방식이다. dfs배운 김에 활용해보고 싶어서 짜봤다.

 

입력받을 때 체크(try-catch)

• 현재 입력받은 노드가 노드번호, (숫자|연산자), 자식정보까지 모두 존재한다면, (숫자|연산자) 자리를 Integer로 바꿔본다. 오류가 난다면 유효하지 않은 연산식이므로 반복을 그만둔다. 따로 if문을 사용하지 않고 try-catch문으로 간단하게 처리해주었다. 
• 입력받으면서 동시에 체크하기때문에, 중간에 유효하지 않은 게 판정되면 for문을 다시 만들어서 나머지 입력값을 소진한다.

boolean check = true;
for(int i=1;i<=N;i++) {
    String[] tmp = in.readLine().split(" ");
    if(tmp.length<=2) {//2초과이면(자식있으면) 부호여야함. 2이하면(자식없으면) 무조건 숫자
        try {
            Integer.parseInt(tmp[1]);
        }
        catch(NumberFormatException e) {
            check=false;
            for(i=i+1;i<=N;i++) in.readLine();
        }
    }
}

//출력
if(check) sb.append(1);
else sb.append(0);

 

입력받고나서 체크

1. 자식이 있는 노드인데 해당 노드가 연산자가 아니거나 자식노드 중 하나라도 유효한 노드가 아닐 때를 체크하는 방법이다.
2. 자식노드라면 숫자인지만 체크한다.

 

equation = new char[N+1];

//탐색
for(int i=1;i<=N;i++) {
    st = new StringTokenizer(in.readLine());
    equation[Integer.parseInt(st.nextToken())] = st.nextToken().charAt(0);
}

//출력
if(dfs(1)) sb.append(1);
else sb.append(0);

//..중략..

public static boolean dfs(int i) {
    int tmp = equation[i]-'0';
    if(i*2<=N && i*2+1<=N) return !(tmp>=0 && tmp<=9) && dfs(i*2) && dfs(i*2+1);
    else return (tmp>=0 && tmp<=9);
}

---

3. 결과

1번 방법

2번 방법

1번 방법이 더 간단한데 실행시간이나 메모리가 더 많이 드는 이유는 예외처리때문인 것 같다. 예외처리도 객체니 예외 객체 생성하는 데 시간이 들지않을까? 속단할 수는 없지만 이 결과만 놓고 보면 재귀함수를 여러번 호출하는 것 보다 예외객체 한 번에 발생하는 비용이 더 크다.

+ 찾아보니 실제로 예외처리 비용이 원래 더 큰게 맞다고 한다. try catch는 이제 필요할 때만 써야겠다. 한 번 시도해본건데 결과가 별로다.