백준 2263번 트리의 순회 with Kotlin

트리의 순회 성공

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

5 초

128 MB

13932

5244

3590

35.113%

문제

n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다.

출력

첫째 줄에 프리오더를 출력한다.

예제 입력 1 복사

3 1 2 3 1 3 2

예제 출력 1 복사

2 1 3

출처

• 잘못된 데이터를 찾은 사람: tncks0121

알고리즘 분류

• 트리
• 분할 정복
• 재귀

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
 
val br = BufferedReader(InputStreamReader(System.`in`))
val bw = BufferedWriter(OutputStreamWriter(System.out))
val n = readLine()!!.toInt()
val inorder = readLine()!!.split(" ").map{it.toInt()}
val postorder =  readLine()!!.split(" ").map{it.toInt()}
val position = IntArray(n+1){0}
fun main()=with(br){
 
 
    for(i in 0 until n){
        position[inorder[i]] = i
    }
 
    preorder(0, n-1, 0 , n-1)
 
    bw.flush()
    bw.close()
}
 
fun preorder(in_start:Int, in_end :Int, post_start:Int, post_end:Int){
    if((in_start > in_end) || (post_start > post_end))
        return
 
    var parents = postorder[post_end]
    print("$parents ")
 
 
    var left = position[parents] - in_start
    var right = in_end - position[parents]
 
 
    preorder(in_start, in_start+left-1, post_start, post_start+left-1)
    preorder(in_end-right+1, in_end, post_end-right, post_end-1)
 
}
 
 
 

http://melonicedlatte.com/algorithm/2018/02/04/145104.html

[백준] 2263번 C/C++ 풀이 _ 트리의 순회 - Easy is Perfect

 

https://velog.io/@bae_mung/Python-BOJ-2263-%ED%8A%B8%EB%A6%AC%EC%9D%98-%EC%88%9C%ED%9A%8C