[Swift 알고리즘] 백준 4933 (뉴턴의 사과)

뉴턴의 사과 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

128 MB

300

91

67

34.184%

문제

두 바이너리 트리 A와 B는 다음과 같은 두 조건을 만족할 때 동등하다고 한다.

1. 두 트리가 비어있다. 또는,

2. 두 트리의 루트가 같다. 또:

(a) A의 왼쪽 서브 트리가 B의 왼쪽 서브 트리와 동등하고, A의 오른쪽 서브 트리가 B의 오른쪽 서브 트리와 동등하다. 또는,

(b) A의 왼쪽 서브 트리가 B의 오른쪽 서브 트리와 동등하고, A의 오른쪽 서브 트리가 B의 왼쪽 서브 트리와 동등하다.

예를 들어, 아래 왼쪽 3개 트리는 서로 동등하다. 하지만, 가장 오른쪽 트리와는 동등하지 않다.

두 바이너리 트리가 주어졌을 때, 동등한지 아닌지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 두 줄로 이루어져 있다. 각 줄은 비교해야 하는 트리의 정보이다.

각 트리의 정보는 포스트오더로 주어진다. 서브트리가 없는 경우에는 nil로 주어진다. 트리의 모든 데이터는 알파벳 대문자이다. 각 줄의 마지막은 end가 있다. 예를 들어, 문제 설명의 가장 왼쪽 그림을 포스트오더로 나타내면 다음과 같다.

nil nil nil G F nil nil C nil nil E nil D B A end

출력

각 테스트 케이스에 대해서, 두 트리가 동등하면 true를, 아니면 false를 출력한다.

예제 입력 1 

2
nil nil nil G F nil nil C nil nil E nil D B A end
nil nil C nil nil E nil D B nil nil G nil F A end
nil nil nil E D nil nil C B nil nil nil G F A end
nil nil nil E C nil nil D B nil nil nil G F A end

예제 출력 1 

true
false

 

 

 

 

풀이 방법

1. 포스트오더 -> 뒤부터 탐색하면 뒤에는 항상 루트

  스스로가 생각하는 포스트오더의 가장 큰 특징은 뒷쪽부터 탐색했을 때 뒤에 Root가 나온다는 사실 입니다.

2. Stack을 활용하여 마지막으로 추가한 혹은 탐색한 Leaf의 left와 right가 채워져 있다면 Stack의 last를 pop()합니다.

3. Equatable Protocol 채택 -> Equatable로 탐색한 Tree가 과연 같은지 확인합니다. 

 

 

예를 들어

postOrder로 "nil" "nil" "D" "nil "nil" "nil" "C" "B" "A" 다음과 같은 입력이 들어왔다고 생각해보겠습니다. 후위 순회하는 방식의 큰 특징은 역순으로 탐색할 경우 Root을 먼저 만납니다. 그래서 우리는 역순으로 탐색할 예정입니다.

 

여기서 Root는 무조건 "A"가 됩니다. Root가 "A"입니다. 이를 스택에 넣으면 다음과 같습니다. 

 

다음에 만나는 문자는 "B"입니다. PrevStack의 Last를 꺼내오고, 만약 RIght이 nil일 경우에는 Right에 새로운 문자 "B"로 만든 Leaf를 삽입 합니다. 

 

 

마찬가지로 "C"를 만날경우도 A가 B를 만났을 경우와 같이 처리해 줍니다.

 

nil을 만날경우는 newLeaf를 생성하지 않고 그냥 right 혹은 left에 추가합니다. 이때 nil은 compiler가 판단하는 optional의 nil이 아닌 String의 "nil"문자열 입니다.

 

 

 

그리고 prev의 left right가 꽉찼다면 stack을 비워줍니다. 

 

 

 

그렇게 다음 문자들을 받으면서 진행하여 stack을 끝까지 비워가며 수행하면 됩니다.

 

 

코드 전문

 

import Foundation

final class TreeLeaf: Equatable {
  static func == (lhs: TreeLeaf, rhs: TreeLeaf) -> Bool {
    return (lhs.left == rhs.left && lhs.right == rhs.right)||(lhs.left == rhs.right && lhs.right == rhs.left)
  }
  var left: String?
  var right: String?
  init (_ l: String?, _ r: String?) {
    left = l
    right = r
  }
  var isFull: Bool {
    return left != nil && right != nil
  }
}
func sol() -> [String: TreeLeaf] {
  var tree: [String: TreeLeaf] = [:]
  let leafArr: [String] = readLine()!.split(separator: " ").map{String($0)}.reversed()
  var prevLeaf: [TreeLeaf] = []
  for ind in 1..<leafArr.count {
    let curString = leafArr[ind]

    while prevLeaf.last != nil && prevLeaf.last!.isFull {
      _ = prevLeaf.popLast()
    }

    if prevLeaf.isEmpty {
    }else {
      let lastLeaf = prevLeaf.popLast()!
      if lastLeaf.right == nil {
        lastLeaf.right = curString
        prevLeaf.append(lastLeaf)
      }else {
        lastLeaf.left = curString
      }
    }
    if curString == "nil" {
      continue
    }
    let newLeaf = TreeLeaf(nil, nil)
    tree[leafArr[ind]] = newLeaf
    prevLeaf.append(newLeaf)
  }
  return tree
}
let N = Int(readLine()!)!
let res = (0..<N).map{_ -> Bool in
  let t1 = sol()
  let t2 = sol()
  return t1 == t2
}
print(res.map{String($0)}.joined(separator: "\n"))