백준 5639번 이진 검색 트리

문제링크: https://www.acmicpc.net/problem/5639

사용한 알고리즘: 그래프이론...?


 '이진검색트리' 를 아는지 확인하는 문제입니다. 문제에서 이진검색트리는 각 노드별로 자신을 기준으로 자신보다 작은 것을 왼쪽, 큰 것을 오른쪽으로 구성합니다. 전위순회결과가 주어지고, 후위순회결과를 출력하는 문제였습니다.

 문제풀이는 다음과 같습니다.
(1) 이진검색트리를 일반 배열로 짜면, [노드개수][왼쪽 오른쪽] = [1000001][2] 의 배열로 짜게 되는데 이는 메모리 초과가 됩니다. 따라서 이것을 그냥 struct로 짜주고 이를 vector에 넣으면 됩니다. 각 struct의 index는 vector에 넣어주는 순서로 생각하고, 각 struct는 자기자신의 값과 왼쪽의 index, 오른쪽의 index를 갖고 있게 만듭니다.

(2) 입력으로 주어지는 각 전위순회결과를 차례로 받아 struct 형태로 vector에 넣습니다. 이후 이것을 갖고 이진검색트리를 만듭니다. (사실 이게 문제의 다입니다...)
i번째 입력(이게 해당 struct의 index)으로 주어지는 value를 struct로 만들어 vector에 넣고, 이진검색트리를 만드는 함수 (Make) 에 ( p번째 value index, i번째 value의 index ) = ( p , i ) 를 넣어줍니다(p = 0으로 시작).  i의 value 가 p의 value 보다 큰지 작은지를 판단해줍니다. 작은 경우를 생각하면 p의 왼쪽에 i 를 넣어주어야 하는데, 이미 다른 값의 index k가 있으면 Make 함수에 다시 ( k, i ) 를 넣어주는 과정을 반복합니다.

(3) 만들어진 이진검색트리를 후위순회로 출력해주면 됩니다.

주의할 점은 주어지는 입력을 끝까지 받아줄때 while(!cin.eof()) 가 아닌 while(cin>>num) 을 써주는 부분입니다. 정확한 이유는 모르지만 전자를 쓸 경우 accepted 되지 않을 것입니다.