백준 2263 트리 풀이 pypy3, python3, java

문제 설명

재귀함수를 이용해 풀었습니다. 각 order의 특징을 살펴보면

inOrder : LVR (왼쪽-뿌리-오른쪽)

postOrder : LRV (왼쪽-오른쪽-뿌리)

preOrder : VLR (뿌리-왼쪽-오른쪽)

이러한 특징을 가졌는데, inOrder와 postOrder를 잘 보시면 구조가 다르기 때문에 이를 이용하여 풀어야 합니다.

1. postOrder는 뿌리의 위치가 항상 맨뒤에 존재합니다. 그래서 매 번 가장 마지막 노드를 가장 먼저 출력합니다.

2. 해당 뿌리 위치 왼쪽까지를 재귀합니다.

3. 해당 뿌리 위치 오른쪽부터 재귀합니다.

4. 1~3을 반복합니다.

문제 후기

pypy3와 python3의 차이점을 몸소 경험했던 문제였습니다.

신선한 충격이었고 덕분에 멘탈이 탈탈 털렸습니다..

이 기회에 이 문제에서 경험했던 pypy3와 python3의 차이점을 포스팅 하도록 하겠습니다.

소스 코드

pypy3

이 코드를 python3로 돌리면 RecursionError가 뜹니다.

또한, 주석처리된 sys.stdout.write를 사용하시면 pypy3에선 메모리 초과(MLE)를 받습니다.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)
N = int(input())
inorder = list(map(int,input().split()))
postorder = list(map(int,input().split()))
pos = [0]*(N+1)
for i in range(N):
    pos[inorder[i]]=i
#VLR - preorder
def solution(inStart,inEnd,postStart,postEnd):
    if inStart>=inEnd or postStart>=postEnd:return
    root = postorder[postEnd-1]
    # sys.stdout.write(str(root)+" ")#V
    print(root,end=" ")
    mid=pos[root]
    leftsize = mid-inStart
    solution(inStart,mid,postStart,postStart+leftsize)#L
    solution(mid+1,inEnd,postStart+leftsize,postEnd-1)#R    
    return

if __name__=="__main__":
    solution(0,N,0,N)

python3

이 코드를 pypy3로 돌리면 메모리 초과(MLE)가 뜹니다.

이유는 sys.setrecursionlimit() 때문인데요, python3는 10**6으로 돌리지 않으면 RecursionError가 뜹니다.

원인을 파악하지 못했습니다... 혹시 아시는 분은 꼭 알려주세요 ㅠㅠ

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
N = int(input())
inorder = list(map(int,input().split()))
postorder = list(map(int,input().split()))
pos = [0]*(N+1)
for i in range(N):
    pos[inorder[i]]=i
#VLR - preorder
def solution(inStart,inEnd,postStart,postEnd):
    if inStart>=inEnd or postStart>=postEnd:return
    root = postorder[postEnd-1]
    sys.stdout.write(str(root)+" ")#V
    mid=pos[root]
    leftsize = mid-inStart
    solution(inStart,mid,postStart,postStart+leftsize)#L
    solution(mid+1,inEnd,postStart+leftsize,postEnd-1)#R    
    return

if __name__=="__main__":
    solution(0,N,0,N)

Java8

import java.io.*;
import java.util.*;
public class Main {
	static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb= new StringBuilder();
	static StringTokenizer st;
	static int N;
	static int[] postorder,inorder,pos;
	static void preorder(int instart,int inend,int poststart,int postend) {
		if(instart>=inend || poststart>=postend)return;
		int root = postorder[postend-1];
		sb.append(root).append(" ");
		int mid = pos[root-1];
		int lens = mid-instart;
		preorder(instart,mid,poststart,poststart+lens);
		preorder(mid+1,inend,poststart+lens,postend-1);
		return;
	}
	public static void main(String[] args) throws IOException{
		N = Integer.parseInt(bf.readLine());
		postorder = new int[N];
		inorder = new int[N];
		pos = new int[N];
		st = new StringTokenizer(bf.readLine());
		for(int i =0;i<N;i++)inorder[i] = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(bf.readLine());
		for(int i =0;i<N;i++)postorder[i] = Integer.parseInt(st.nextToken());
		for(int i =0;i<N;i++)pos[inorder[i]-1] = i;
		preorder(0,N,0,N);
		System.out.println(sb);
	}
}