[파이썬] 1233. 사칙연산 유효성 검사

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

사칙연산으로 구성되어 있는 식은 이진 트리로 표현할 수 있다.

아래는 식 “(8/2)*(6-4)”을 이진 트리로 표현한 것이다.

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

 

 

사칙연산 “+, -, *, /”와 양의 정수로만 구성된 임의의 이진 트리가 주어질 때, 이 식의 유효성을 검사하는 프로그램을 작성하여라.

여기서 말하는 유효성이란, 사칙연산 “+, -, *, /”와 양의 정수로 구성된 임의의 식이 적절한 식인지를 확인하는 것으로, 계산이 가능하다면 “1”, 계산이 불가능할 경우 “0”을 출력한다.

(단, 계산이 가능한지가 아닌 유효성을 검사하는 문제이므로 0으로 나누는 경우는 고려하지 않는다. )

 

 

[제약 사항]

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

총 노드의 개수는 200개를 넘어가지 않는다.

트리는 완전 이진 트리 형식으로 주어지며, 노드당 하나의 연산자 또는 숫자만 저장할 수 있다.

노드는 아래 그림과 같은 숫자 번호대로 주어진다.
 

 

[입력]

각 테스트 케이스의 첫 줄에는 각 케이스의 트리가 갖는 정점의 총 수 N(1≤N≤200)이 주어진다.

그 다음 N줄에 걸쳐 각각의 정점 정보가 주어진다.

해당 정점에 대한 정보는 해당 정점의 알파벳, 해당 정점의 왼쪽 자식, 오른쪽 자식의 정점번호가 차례대로 주어진다.

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

입력에서 이웃한 숫자 또는 연산자, 자식 정점의 번호는 모두 공백으로 구분된다.

위의 예시에서, 숫자 8이 4번 정점에 해당하면 “4 8”으로 주어지고, 연산자 ‘/’가 2번 정점에 해당하면 두 자식이 각각 숫자 ‘8’인 4번 정점과 숫자 ‘2’인 5번 정점이므로 “2 / 4 5”로 주어진다.

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

[출력]

#부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 테스트 케이스의 정답을 출력한다.

 

입력

너무 길어서 생략

 

출력

#1 0
#2 0
.......

 

 

 

🥩 나의 풀이

 

for test_case in range(10):
  N=int(input())      # 정점의 총 수
  result=1
  for n in range(N) :
    info=list(input().split())    # 정점 번호, 숫자 or 연산자, 왼쪽 자손, 오른쪽 자손
    if info[1].isdigit() == 0 :   # 연산자면 왼쪽 자손, 오른쪽 자손 다 있어야 함
      if len(info) < 4 :		# 입력 최대 길이 4가 되어야 함.
        result=0    # 유효성 검사 통과 실패
  
  print(f"#{test_case+1} {result}")

 

입력 값만으로 유효성 검사를 할 수 있음.

연산자 노드는 왼쪽 자손, 오른쪽 자손을 갖고 있어야 함.

 

# 실패한 코드
def in_order(v):
  if v <= N :
    in_order(v*2)   # 왼쪽
    if tree[v][0].isdigit():
      return 0
    in_order(v*2+1) # 오른쪽
  return 1		# 계산 가능

for test_case in range(10):
  N=int(input())      # 정점의 총 수
  tree=[0]*(N+1)

  for n in range(N) :
    info=list(input().split())     # 정점 번호, 숫자 or 연산자, 왼쪽 자손, 오른쪽 자손
    tree[int(info[0])]=info[1:]      # 숫자 or 연산자

  #print(tree)  
  print(f"#{test_case+1} {in_order(1)}")

 

반만 통과한 코드.

부모 노드가 숫자면 return 0하도록 만듦.

알고리즘에 구멍이 있음.

 

 

🥞 다른 사람 풀이

 

# 출처  https://sweetlog.netlify.app/problem/swea_1233/

def inorder(node):
  if node :
    inorder(tree[node][2])    # 왼쪽
    formula.append(tree[node][1])    # 연산자 or 숫자
    inorder(tree[node][3])    # 오른쪽

for tc in range(10) :     # 10개의 테스트 케이스
  n=int(input())        # 총 정점의 수
  tree=[[0 for _ in range(4)] for _ in range(n+1)]    # 열 =  정점 번호, 해당 정점의 알파벳, 해당 정점의 왼쪽 자식, 오른쪽 자식의 정점번호
  
  # 정점의 수만큼 입력받음.
  for line in range(n):
    tmp=list(input().split())
    index=int(tmp[0])  		 # 노드 번호
    tree[index][0]=index
    if len(tmp) >= 3 :
      tree[index][2]=int(tmp[2])    # 해당 정점의 왼쪽 자식
    if len(tmp) == 4 :
      tree[index][3]=int(tmp[3])    	# 오른쪽 자식의 정점 번호
    tree[index][1]=tmp[1]     	# 해당 정점의 알파벳

  formula=[]
  inorder(1)
  result=1      # 유효성 검사 통과

  for i in range(len(formula)):
    if not i%2 :    # i%2가 0(짝수)이면 True
      if ord(formula[i]) < 48 or ord(formula[i]) >= 58 :    # '0'이 48, '9'가 57
        result=0      # 유효성 검사 통과 실패
        break
    else:   # 홀수면
      if formula[i] not in ['-', '+', '*', '/']:  # 연산자가 아니면
        result=0
        break

  print(f"#{tc+1} {result}")

 

중위 순회로 식을 완성한 후 for문으로 유효성 검사를 한다.

짝수 노드 번호에는 연산자, 홀수 노드 번호가 숫자가 아니면 result=0으로 유효성 검사 실패.

 

# 출처 https://smilelife12.github.io/Algorithm-SW1233/
import math

oper = ['+','-','*','/']
T = 10

def DFS(vis, ar, num):
    left = num*2
    right = num*2 + 1
    if left >= len(vis):
        return
    vis[left] = 1
    if ar[left] is 1:     # 연산자면
        DFS(vis, ar, left)
    if right >= len(vis):
        return
    vis[right] = 1
    if ar[right] is 1:
        DFS(vis, ar, right)

for test_case in range(T):
    N = int(input())		# 총 정점의 수
    depth = len(bin(N)) - 2		# 2의 x승 보다 작다는 것을 표현
    can_oper = True
    arr = [0] *(N+1)
    for i in range(1,N+1):    # 노드 번호 1부터 시작
        t = list(input().split())
        if t[1] in oper:
            if i >= math.pow(2, depth-1) :    # 거듭제곱
                can_oper = False
            else:
                arr[i] = 1    # 연산자면
    if can_oper:
        visit = [0]*(N+1)
        for i in range(1,N+1):
            if visit[i] is 0:
                visit[i] = 1	# 방문 처리
                if arr[i] is 1:     # 연산자면
                    DFS(visit, arr, i)
    else:
        print("#"+str(test_case+1)+" 0")
        continue
    if 0 in visit[1:]:
        print("#" + str(test_case + 1) + " 0")
    else:
        print("#" + str(test_case + 1) + " 1")

 

나중에 다시 한 번 더 이해 필요

 

 

 

 

 

문제 출처 SW expert academy