[백준/브루트포스] 4970번 디지털 회로개론

https://www.acmicpc.net/problem/4970

4970번: 디지털 회로 개론

이 문제는 식이 주어졌을 때 3차 논리에서 2로 만드는 (P,Q,R) 쌍의 개수를 찾는 문제이다.

 

3차 논리에서 0,1,2 밖에 없고, P,Q,R 쌍을 찾는 것이므로 브루트포스를 진행했을 때

반복문을 9번만 돌려도 되어서, 브루트 포스 방법을 사용했다.

 

우선 주어진 식을 정리하였는데,

 

자료구조 시간에 배운 후위표기법이 생각나서 스택을 사용하여 후위표기법으로 바꾸었다.

이 때, 단항 연산자인 Not을 먼저 계산해줘야 하므로 우선 순위를 높게 잡았다.

 

후위 표기법으로 바꾼 후에, 다시 스택을 이용하여 3차 논리에 맞춰서 식을 계산해주었다.

 

import sys
input = sys.stdin.readline

#단항연산자가 우선순위가 큼
prec = {'-':3,'+':2,'*':2,'(':1}

#3차 논리
NOT = [2,1,0]
AND = [[0,0,0],[0,1,1],[0,1,2]]
OR = [[0,1,2],[1,1,2],[2,2,2]]

#후위 표기법
def postfix(s):
    stack = []

    answer = ''

    for c in s:
        if c not in "()+*-":
            answer += c
        elif c == "(":
            stack.append(c)
        elif c == ")":
            while stack[-1] != "(":
                answer += stack.pop()
            stack.pop()
        elif stack and prec[c] <= prec[stack[-1]]:
            answer += stack.pop()
            stack.append(c)
        else:
            stack.append(c)
    while stack:
        answer += stack.pop()

    return answer

#후위표기법 계산
def cal(s):
    stack = []
    for t in s:
        if t == "*":
            stack.append(AND[stack.pop()][stack.pop()])
        elif t == "+":
            stack.append(OR[stack.pop()][stack.pop()])
        elif t == "-":
            stack.append(NOT[stack.pop()])
        else:
            stack.append(int(t))
    return stack.pop()

while True:
    sent = input().strip()
    
    if sent == ".": break

    #-- => 없애기
    sent = sent.replace("--","")

    #후위 표기법으로 바꾸기
    pos = postfix(sent)

    cnt = 0

    for p in ['0','1','2']:
        new_1 = pos.replace('P',p)
        for q in ['0','1','2']:
            new_2 = new_1.replace('Q',q)
            for r in ['0','1','2']:
                new_3 = new_2.replace('R',r)

                ans = cal(new_3)
                if ans == 2: cnt += 1
    print(cnt)