[파이썬] 1232. 사칙연산

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.

사칙연산으로 구성되어 있는 식은 이진 트리로 표현할 수 있다. 아래는 식 “(9/(6-4))*3”을 이진 트리로 표현한 것이다.

임의의 정점에 연산자가 있으면 해당 연산자의 왼쪽 서브 트리의 결과와 오른쪽 서브 트리의 결과를 사용해서 해당 연산자를 적용한다.

 

사칙연산 "+, -, *, /"와 양의 정수로만 구성된 임의의 이진트리가 주어질 때, 이를 계산한 결과를 출력하는 프로그램을 작성하라.

단, 중간 과정에서의 연산은 실수 연산으로 하되, 최종 결과값이 정수로 떨어지지 않으면 정수부만 출력한다.

위의 예에서는 최종 결과값이 13.5이므로 13을 출력하면 된다.

 

[제약 사항]

정점의 총 수 N은 1 <= N <= 1000

 

[입력]

각 테스트 케이스의 첫 줄에는 각 케이스의 트리가 갖는 정점의 총 수 N(1 <= N <= 1000)이 주어진다. 그 다음 N줄에 걸쳐 각각의 정점 정보가 주어진다.

정점이 단순한 수이면 정점번호와 해당 양의 정수가 주어지고, 정점이 연산자이면 정점번호, 연산자, 해당 정점의 왼쪽 자식, 오른쪽 자식의 정점번호가 차례대로 주어진다.

정점번호는 1부터 N까지의 정수로 구분된다. 입력에서 정점 번호를 매기는 특별한 규칙은 없으나, 루트 정점의 번호는 반드시 1이다.

입력에서 이웃한 수나 연산자는 모두 공백으로 구분된다.

위의 예시에서, 숫자 4가 7번 정점에 해당하면 "7 4"으로 주어지고, 연산자 '/'가 2번 정점에 해당하면 두 자식이 각각 숫자 9인 4번 정점과 연산자 '-'인 5번 정점이므로 "2 / 4 5"로 주어진다.

총 10개의 테스트 케이스가 주어진다.

 

[출력]

#부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 테스트 케이스에 대한 답을 출력한다. 답은 항상 정수값으로 기록한다.

 

출력

#1 13

#2 20

 

 

🧀 나의 풀이

 

def postorder(v):	# 후위 순회
    if v >= N:			
        return
    if tree[v][2] > 0 :  	
        postorder(tree[v][2])	# 왼쪽 자식
    if tree[v][3] > 0 :  	
        postorder(tree[v][3])	# 오른쪽 자식
	
    # 연산자에 계산 결과 업데이트해야 다음 연산자 노드에서 계산 가능
    if tree[v][1] == '+':
    	# 왼쪽 노드와 오른쪽 노드 더하기
        tree[v][1] = tree[tree[v][2]][1] + tree[tree[v][3]][1]  
    elif tree[v][1] == '-':
    	# 왼쪽 노드와 오른쪽 노드 뺄셈
        tree[v][1] = tree[tree[v][2]][1] - tree[tree[v][3]][1]  
    elif tree[v][1] == '*':
    	# 왼쪽 노드와 오른쪽 노드 곱셈
        tree[v][1] = tree[tree[v][2]][1] * tree[tree[v][3]][1]  
    elif tree[v][1] == '/':
    	 # 왼쪽 노드와 오른쪽 노드 뺄셈
        tree[v][1] = tree[tree[v][2]][1] / tree[tree[v][3]][1] 
        
for test_case in range(10):		# 10개의 테스트 케이스
    N = int(input())  	# 정점의 총 수
    tree = [[0] * 4 for _ in range(N + 1)]  	# 1 인덱스부터 시작해서 N+1
    # 트리 입력
    for n in range(N):  	
        info = list(input().split())
        if info[1].isdigit() :      # 숫자면
            tree[int(info[0])][1]=int(info[1])
        else :
            tree[int(info[0])][1]=info[1]       # 연산자
            tree[int(info[0])][2] = int(info[2])    # 왼쪽 자식
            tree[int(info[0])][3] = int(info[3])    # 오른쪽 자식

    postorder(1)
    print(f"#{test_case+1} {int(tree[1][1])}")

 

첨엔 cnt를 만들어서 계산 결과를 업데이트 했다.

이렇게 하면 2번째 계산 때 오류난다. 

첫 번째 테스트 케이스 예시

v가 1일 때 elif tree[v][1] == '-':
        cnt += tree[tree[v][2]][1] - tree[tree[v][3]][1]   # 잘못된 코드 예시

에서 tree[tree[v][2]][1]가 -다. 계산불가..

계산 끝나면 연산자를 계산 결과로 업데이트해야한다.

 

 

 

🍖 다른 사람 풀이

 

# 출처 https://swbeginner.tistory.com/entry/SWEA-%EC%BD%94%EB%94%A9-SW-%EB%AC%B8%EC%A0%9C%ED%95%B4%EA%B2%B0-%EA%B8%B0%EB%B3%B8-%EC%82%AC%EC%B9%99%EC%97%B0%EC%82%B0-PYTHON-1232?category=872331
for tc in range(1, 11):		# 10개의 테스트케이스
  # 노드의 수
  n=int(input())

  # str값으로 받음
  # 정점의 값이 1부터 들어와서 앞에 리스트 하나 추가해서 index값 맞추기
  nodes=[[0]]+[list(input().split()) for _ in range(n)]

  # 부모 노드, 현재 값, 사칙연산
  board=[[0, 0, 0] for _ in range(n+1)]

  for q in range(n+1) :
    # 정점이 연산자인 경우
    if len(nodes[q]) == 4 :
      idx, car, left, right=nodes[q]

      # 현재 위치에 사칙연산 입력
      # 자식 노드에 부모 노드 값 입력
      board[q][2]=car
      board[int(left)][0]=q
      board[int(right)][0]=q
    
    # 정점이 단순 수인 경우
    elif len(nodes[q]) == 2 :
      idx, num=nodes[q]

      # 현재 위치에 수 입력
      board[q][1]=int(num)

  for w in range(n//2):
    # 2*n이랑 2*n+1이랑은 한 쌍
    # 2*n위치의 부모 값을 확인하고
    # 2*n과 2*n+1과 부모 값에 입력된 연산자로 연산
    # 나온 값을 부모 노드의 현재 값에 입력
    if board[board[n-2*w-1][0]][2] == '+' :
      board[board[n-2*w-1][0]][1] = board[n-2*w-1][1]+board[n-2*w][1]
    elif board[board[n-2*w-1][0]][2] == '-' :
      board[board[n-2*w-1][0]][1] = board[n-2*w-1][1]-board[n-2*w][1]
    elif board[board[n-2*w-1][0]][2] == '*' :
      board[board[n-2*w-1][0]][1] = board[n-2*w-1][1]*board[n-2*w][1]
    else :
      board[board[n-2*w-1][0]][1] = board[n-2*w-1][1]/board[n-2*w][1]
  print('#{} {}'.format(tc, int(board[1][1])))

 

nodes에 다 입력 받고 반복문으로 열의 길이에 따라서 board에 값을 입력한다.

idx, car, left, right=nodes[q]를 하면 각각의 변수에 0~3 인덱스 값이 들어간다.

재귀를 사용하는 대신 board[board[n-2*w-1][0]][2]를 사용해서 후위 순회하는 것 처럼 구현.

연산자에 계산 값을 넣는다.

 

 

 

 

 

문제 출처 SW expert academy