문제

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

문제 분석

이 문제에서 사용되는 연산자는 총 3가지이다, NOT, OR, AND. NOT은 단일항연산자고 OR와 AND는 이항연산자다. 그래서 연산자가 요구하는 숫자의 개수가 NOT은 1개 OR, AND는 2개라 본다. 또한 표는 문제에 나와있으므로 저거 그대로 내보낼 수 있도록 구현하면 된다.

AND와 OR은 항상 괄호로 둘러 쌓여 있으므로 같은 연산자가 이어져서 나오는 케이스는 고려할 필요가 없다.

(A+B+C+D) 같은 경우는 고려할 필요가 없다는 뜻.

변수 P, Q, R 은 0,1,2 어떤 수가 들어와도 된다.

입력이 80글자를 넘지 않는다.되게 짧다.

주어진 식을 2로 만드는 P,Q,R의 쌍의 개수를 물어봤으니 모든 경우를 살펴보면 27번 돌게 된다. 근데 입력이 80글자를 넘지 않으므로 입력을 1자로 훑으면서 PQR를 0,1,2로 변환하는데 걸리는 총시간을 80 * 27, 2160이며, 대단히 낮은 수준이다.

그러면 아래 포뮬러를 계산해주는 함수를 만들고, PQR은 삼중 FOR문으로 P,Q,R에 들어갈 수 있는 모든 케이스로 계산하며, 결과가 2가 나오는 것만 체크하면 되는게 아닌가 생각이 들었다.

<formula> ::= 0 | 1 | 2 | P | Q | R |
              -<formula> | (<formula>*<formula>) | (<formula>+<formula>)

문제 풀이

기본 연산자 알고리즘

def minus(x):
    if x == 0 :
        return 2
    elif x == 1:
        return 1
    elif x == 2:
        return 0
    else:
        raise Exception
    
def multi(x,y):
    if x == 0 or y == 0 :
        return 0
    elif x != 2 or y != 2 : 
        return 1
    else:
        return 2
    
def plus (x,y):
    if x == 2 or y == 2 :
        return 2
    elif x != 0 or y != 0 : 
        return 1
    else:
        return 0
    

연산 함수

시키는 대로 구현했음.

아래는 입력된 글자들을 재귀적으로 연산하는 함수

if sentence == "0" or sentence == "1"  or sentence =="2":
        return int(sentence)
    elif sentence[0] == "-":
        
        # Not op process
        absNum = ""
        notNum = False
        isFirst = True
        for i,c in enumerate(sentence) :
            if c == "-" and isFirst == True:
                notNum = not notNum
            else:
                absNum += c
                isFirst = False
        result = execute(absNum)
        if notNum == True:
            result = minus(result)
        return result 
    elif sentence[0] =="(": 
        # and , or op process
        left = ""
        right = ""
        
        paraNum = 0
        buffer = ""
        op = ""
        
        for i in range(len(sentence)):
            #print("Debug buffer : ", buffer)
            if sentence[i] == "(" and paraNum == 0:
                paraNum += 1
            elif sentence[i] == ")" and paraNum == 1:
                right = buffer 
                buffer = ""
                paraNum -= 1
            elif sentence[i] == "(" and paraNum > 0 :
                paraNum += 1
                buffer += sentence[i]
            elif sentence[i] == ")" and paraNum > 1:
                paraNum -= 1
                buffer += sentence[i]
            elif paraNum == 1 and (sentence[i] == "+" or sentence[i] == "*"):
                op = sentence[i]
                left = buffer
                buffer = ""
            else:
                buffer += sentence[i]
            
        if op == "+":
            return plus(execute(left) , execute(right))
        elif op == "*":
            #print("Debug ",left, right)
            return multi(execute(left), execute(right))
        else:
            raise Exception

이부분은 특별한건 없고 fomular의 문법을 그대로 옮긴 것이다. 그래도 코드가 긴 편이니 나눠서 확인해보자.

formula ::= 0 | 1 | 2 인 경우

if sentence == "0" or sentence == "1"  or sentence =="2":
        return int(sentence)

그냥 그대로 반환하면 된다.

formula ::= P | Q | R 인 경우

얘내들은 각각의 쌍에 0, 1, 2를 넣어준 후 테스트를 할 것이므로 연산함수에서는 신경쓰지 않아도 된다.

formula ::= -formula

elif sentence[0] == "-":
        
        # Not op process
        absNum = "" 
        notNum = False
        isFirst = True
        for i,c in enumerate(sentence) :
            if c == "-" and isFirst == True:
                notNum = not notNum
            else:
                absNum += c
                isFirst = False
        result = execute(absNum)
        if notNum == True:
            result = minus(result)
        return result 

앞에 -가 이어서 나온뒤 다른 것이 나오는 케이스다. 주의 할 점은 - 이후 괄호문이 나올 수 있어서 그 부분도 신경을 써야한다.

formula ::= (formula*formula) | (formula+formula) 인 경우

# and , or op process
        left = ""
        right = ""
        
        paraNum = 0
        buffer = ""
        op = ""
        
        for i in range(len(sentence)):
            #print("Debug buffer : ", buffer)
            if sentence[i] == "(" and paraNum == 0:
                paraNum += 1
            elif sentence[i] == ")" and paraNum == 1:
                right = buffer 
                buffer = ""
                paraNum -= 1
            elif sentence[i] == "(" and paraNum > 0 :
                paraNum += 1
                buffer += sentence[i]
            elif sentence[i] == ")" and paraNum > 1:
                paraNum -= 1
                buffer += sentence[i]
            elif paraNum == 1 and (sentence[i] == "+" or sentence[i] == "*"):
                op = sentence[i]
                left = buffer
                buffer = ""
            else:
                buffer += sentence[i]
            
        if op == "+":
            return plus(execute(left) , execute(right))
        elif op == "*":
            return multi(execute(left), execute(right))
        else:
            raise Exception

괄호가 시작한다는 건 +나 가 무조건 나온다는 것. 이는 +나 를 기준으로 왼쪽 오른쪽 항이 나뉜다는 걸 의미한다.

이에 괄호 (의 개수와 괄호 )의 개수가 얼마나 나왔는지로 괄호의 깊이를 계산하며, 괄호의 깊이가 1일때 연산자를 기준으로 좌항, 우항 나눠서 들어감.

while True:
            
    s = input()
    if  s== "."    :
        break
    else:
        answer = 0
        for p in range(3):
            #print(p)
            temp = []
            for c in s:
                if c=="P":
                    temp.append(str(p))
                else:
                    temp.append(c)
            tempLen = len(temp)
            for q in range(3):
                temp2 = []
                for c in temp:
                    if c=="Q":
                        temp2.append(str(q))
                    else:
                        temp2.append(c)
                             
                for r in range(3) :
                    temp3 = []
                    for c in temp2:
                        if c=="R":
                            temp3.append(str(r))
                        else:
                            temp3.append(c)
                    #print("Debug origin sentence : ", "".join(temp3))
                    result = execute("".join(temp3)) 
                    #result = 2           
                    #print("Debug", result)
                    if result == 2 :
                        answer += 1

        print(answer)

시작 FOR문인데, S가 .으로 들어오면 반복문 종료함. 아니라면 P에 0,1,2 대체. 그다음 Q에 0,1,2 대체. 그다음 R에 0,1,2 교체해서 연산 함수를 돌리고 그 결과 2라면 ANSWER 를 +1 함.