글 읽기 - 반례 부탁드립니다ㅠㅠ

hans081545 5년 전 0

트리 생성후 삭제는 실제 노드를 삭제 한게 아닌 리프를 찾을때 입력값으로 주어진 노드 방향으로 리프를 찾지 않게끔 하였습니다.

주어진 예제를 입력해 봐도 제대로 정답이 나오는데 코드를 제출하면 항상 틀렸다고 나오네요...

반례 혹은 제 코드중 잘못된 부분이 있다면 한수 가르켜 주셨으면 합니다. ㅠ

var removeNodeNum: Int?
var lefNum: Int = 0

class TreeNode {
    
    var value: Int?
    var parent: TreeNode?
    var leftChild: TreeNode?
    var rightChild: TreeNode?
    
    public convenience init(value: Int) {
        self.init(value: value, left: nil, right: nil, parent:nil)
    }
    
    public init(value : Int, left: TreeNode?, right: TreeNode?, parent: TreeNode?) {
        
        self.value = value
        self.leftChild = left
        self.rightChild = right
        self.parent = parent
        
    }
    
    func addNode(value: Int, parent: Int) {
        
        if parent == -1 {
            return
        }
        
        let pNode = searchParent(parent: parent)
        
        if pNode?.leftChild == nil {
            
            pNode?.leftChild = TreeNode.init(value: value, left: nil, right: nil, parent: pNode)
            
        } else {
            
            pNode?.rightChild = TreeNode.init(value: value, left: nil, right: nil, parent: pNode)
            
        }
        
    }
    
    func searchParent(parent: Int) -> TreeNode? {
        
        var pNode: TreeNode?
        
        if self.value == parent {
            
            pNode = self
            
        } else {
            
            if self.leftChild != nil {
                
                pNode = self.leftChild?.searchParent(parent: parent)
                
            }
            
            if self.rightChild != nil, pNode == nil {
                
                pNode = self.rightChild?.searchParent(parent: parent)
                
            }
            
        }
        
        return pNode
        
    }
    
    func getLefCnt() {
        
        if self.leftChild != nil && self.leftChild?.value != removeNodeNum {
            
            self.leftChild?.getLefCnt()
            
        }
        
        if self.rightChild != nil && self.rightChild?.value != removeNodeNum {
            
            self.rightChild?.getLefCnt()
            
        }
        
        if self.leftChild == nil && self.rightChild == nil {
            
            lefNum += 1
            
        }
        
    }
    
}

func main() {
    
    guard let strN = readLine() else { return }
    guard let n = Int(strN) else { return }
    
    var tempArr = Array.init(repeating: 0, count: n)
    guard let strPArr = readLine()?.split(separator: " ") else { return }
    var tree: TreeNode?
    
    for i in 0..<n {
        
        tempArr[i] = Int(strPArr[i])!
        if -1 == Int(strPArr[i])! {
            tree = TreeNode.init(value: i)
        }
        
    }
    
    for i in 0..<n {
        
        tree?.addNode(value: i, parent: tempArr[i])
        
    }
    
    guard let strRemoveNode = readLine() else { return }
    guard let removeNode = Int(strRemoveNode) else { return }
    removeNodeNum = removeNode
    
    tree?.getLefCnt()
    print(lefNum)
    
}

main()

khj94811 5년 전 1

문제에는 주어지는 트리가 이진트리라고 써져있지 않습니다.

hans081545 5년 전 0

아하... 감사합니다. 다시 풀어봐야겠네요!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례 부탁드립니다ㅠㅠ

hans081545 5년 전 0

khj94811 5년 전 1

hans081545 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말