백준 4882 자바 - 정규형 (BOJ 4882 JAVA)

문제 : boj4882

 

 

  지문에 제대로 낚였다.. 문제를 잘못이해해서 꽤 오래동안 맞왜틀 외치고 있었다. ㅠ

 

  가장 깊은 레벨부터 AND로 지정하고, 이후 올라갈수록(레벨 숫자가 낮아질수록) AND - OR - AND - OR - ... 이렇게 지정해야 하는 문제였다.

 

  문제 예시에서 '가장 위'가 AND라고 멋대로 생각해버린데다가 한글 번역본에서 '가장 낮은 레벨에 있는 트리는 AND 트리'라고 해버려서 당연히 '낮은' 레벨이니깐 레벨1부터 AND라고 계속 생각하고 맞왜틀 외치고 있었음 ㅡㅡ; 심지어 예제도 그렇게 풀면 다 맞다;; 결론적으로 도저히 내 코드에 문제점을 못찾겠어서 혹시나하고 영어 원본으로 보고 알아채고 맞출 수 있었다('The trees at the deepest level are AND-trees.'). 아니 근데 '가장 낮은 레벨' 보다는 '가장 깊은 레벨'이 더 명확하지않나.. ㅠ 실제로도 구글링해보니 '낮은 레벨'은 다들 혼용해서 쓰고 있다 ㅋㅋ

 

 

  아무튼 징징은 여기까지하고, 해설을 해보겠다.

이 문제를 풀 때 필요한건, '가장 깊은 레벨이 몇인지 알 수 있어야함', '닫는 괄호를 만났을 때, 현재 트리의 레벨이 몇인지 알 수 있어야함' 이 두개만 알면 된다.

전자는 가장 깊은 레벨부터 AND - OR - AND - ... 이렇게 정해야 하므로 알아야 한다.

후자는 실제 true, false를 계산하기 위해 필요하다.

 

A.

  뭐 트리로 그려져 있는 문제이니 트리로 풀어야겠다고 생각할 수 있는데, 스택에 '(', 'T', 'F'는 넣고, ')'를 만날 경우 스택에서 '('가 나올 때 까지 전부 빼버리는식으로 진행하면 현재 트리의 레벨을 더 간단하게 알 수 있다. 이 때, 레벨은 '('가 들어갈 때 1을 증가하면 되고, ')'를 만나서 '('를 만날 때 까지 'T','F'를 빼면서 계산하고 '('를 뺄 때 감소시키면 된다.

예를들어 ((TFT)T)는 다음과 같은 과정으로 구할 수 있다.

 

 

1. 시작은 다음과 같다. Level은 현재 계산중인 트리의 레벨이고 우측에 컵같은건 '스택'을 의미한다.

 

 

2. '('을 스택에 넣고 레벨을 증가시킨다.

 

 

3. 다음 '('을 넣고 레벨을 증가시킨다.

 

4. 마찬가지로 T,F,T도 넣는다. '('가 아니므로 레벨은 변경되지 않는다.

 

5. 다음으로 ')'를 만났다. 그럼 스택에서 하나씩 빼면서 '('가 나올 때 까지, 현재 레벨인 '2'에 따른 AND 또는 OR을 적용하면 된다. 뭘 해줘야할지 정하는 방법은 이따 다시 얘기할꺼고, 일단 여기서는 AND를 하면 된다. T and F and T = F 이다.

 

6. 그럼 이제 '('까지 봤으니, '('는 빼주고, 레벨을 1 감소시켜주고, '5'에서 계산한 결과인 'F'를 다시 스택에 넣어준다.

 

7. 이제 'T'가 나왔으니 마찬가지로 스택에 넣어준다.

 

8. 다시 ')'가 나왔으니 마찬가지로 '('를 만날 때 까지 빼주면서 현재 레벨인 '1'에 해당하는 연산을 해주면 된다. 예시 케이스에서는 레벨 1에서 'OR'을 해주면 된다. T or F = T이다. 마찬가지로 '('를 빼고, 레벨을 감소시키고, 계산 결과를 다시 스택에 넣는다.

 

9. 이제 문자열을 모두 다 봤으니, 최종적으로 스택에 남은 'T'가 답이다.

 

 

 

B.

  그럼 위를 통해 답을 찾는방법은 알았으니, 이제 다음으로 레벨에 따라 AND, OR 중 어떤 연산을 택할지 알아보자. 위의 예시를 설명하면서 가장 깊은 레벨은 몇이었냐면 '2'이다. 그럼 'The trees at the deepest level are AND-trees.'에 따라 '2'는 AND, '1'은 OR을 해주면 된다. 다만 이걸 처음부터 알고있어야 위의 1~9의 과정에서 연산에 적용할 수 있다.

 

  어떻게 미리 알 수 있냐면, 위의 과정에서 스택을 가지고 연산하는 과정만 빼버리고, 괄호를 만났을 때 level을 증가하거나 감소시키는 부분만 미리 돌려 그 중 최대치였던 레벨을 구하면 된다. (코드에서도 getDeepestLevel로 미리 최대 깊이를 구하고, 위의 과정을 진행한다.). 그럼 최대 깊이의 레벨을 maxLevel이라고 하고 현재 레벨을 curLevel이라고 할 시, 적용할 연산은 (maxLevel - curLevel)이 짝수라면 AND, 홀수라면 OR을 적용하면 된다.

 

 

C.

  이제 계산방법도 알았고 레벨에 따라 OR, AND 중 뭘 써야할지도 알았다. 그럼 'T', 'F' 문자들을 가지고 OR, AND 연산은 어떻게 할 수 있을까? 뭐 여러 방법이 있을텐데, 내 경우엔 심플하게 T는 1, F는 0으로 바꿔서 스택에 넣었다. 그럼 0과 1에 대한 bitAND(&), bitOR(|) 결과값은 다음과 같다.

  위의 결과들은 true, false에 대한 and, or의 논리표와 동일하므로 1,0에 대한 bitOR, bitAND 연산으로 대체해서 계산해도 상관없다. 최종적으로 스택에 1이 남았다면 true를 출력, 0이 남았다면 false를 출력했다.

 

 

 

코드 : github

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

public class Main {
    private static final int OPEN_BRACKET   = 2;
    private static final int TRUE           = 1;
    private static final int FALSE          = 0;

    private int getDeepestLevel(String s) {
        int maxLv = 0;
        int lv = 0;
        for (int i = 0; i < s.length(); i++) {
            switch (s.charAt(i)) {
                case '(' : lv++; maxLv = Math.max(maxLv, lv); break;
                case ')' : lv--; break;
            }
        }
        return maxLv;
    }

    private boolean getTreeResult(String s) {
        int lv = 0;
        int maxLv = getDeepestLevel(s);
        Stack<Integer> stk = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            switch (s.charAt(i)) {
                case '(' : lv++; stk.push(OPEN_BRACKET); break;
                case 'T' : stk.push(TRUE); break;
                case 'F' : stk.push(FALSE); break;
                case ')' :
                    int tmp = stk.pop();
                    while (stk.peek()!=OPEN_BRACKET) {
                        if (((maxLv-lv)&1) == 0) tmp &= stk.pop();
                        else tmp |= stk.pop();
                    }
                    stk.pop();
                    lv--;
                    stk.push(tmp);
                    break;
            }
        }

        return stk.pop() == 1 ? true : false;
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = 1;
        StringBuilder answer = new StringBuilder();
        while (true) {
            String s = br.readLine();
            if (s.charAt(1) == ')') break; // EOF
            answer.append(tc++).append('.').append(' ').append(getTreeResult(s) ? "true" : "false").append('\n');
        }
        System.out.print(answer);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}