강승현입니다
article thumbnail
반응형

문제로이동


목차

     



    문제 설명

    재귀함수를 이용해 풀었습니다. 각 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);
    	}
    }
    반응형
    profile

    강승현입니다

    @CODe_

    포스팅에 대한 피드백을 환영합니다!
    피드백 작성자를 존중하며, 함께 공유하고 성장할 수 있는 기회가 되기를 기대합니다.의견이나 조언이 있다면 언제든지 자유롭게 남겨주세요!

    article prev thumbnail
    article next thumbnail
    profile on loading

    Loading...