백준 2263번 (java)

byeol·2023년 3월 21일
0

오늘 푼 문제는 맞았다.
근데 너무 오래 고민해서 사실상 틀렸다고 봐야한다.

이 문제는 어렵지는 않은데 조금 복잡하다.

접근

https://www.acmicpc.net/problem/2263

일단 이 문제는 인오더와 포스트오더를 주고 프리오더를 구하라는 문제이다.

일단 이 문제는 아래와 같은 흐름으로 접근했다.

  • 먼저 루트노트와 연결된 왼쪽 자식 노드의 번호, 오른쪽 자식 노드의 번호를 배열에 저장하자.
    arr[n+1][2]개의 배열에서 행의 index가 root노드의 번호가 되고 0번째 열에는 root노드의 왼쪽 자식 노드 번호, 1번째 열에는 root노드의 오른쪽 자식 노드 번호를 입력한다.
  • 재귀함수
      1. 규칙을 발견해서 root노드와 오른쪽 자식노드, 왼쪽 자식 노드 찾아서 배열에 저장
      1. 왼쪽 트리와 오른쪽 트리 나누고
        재귀함수(왼쪽트리) , 재귀함수(오른쪽트리) 호출
  • 마지막에 배열에 모든 값이 저장되며 이를 프리오더로 출력하는 함수를 만든다.

과정

위와 같은 트리가 있다고 가정할 때

인오더와 포스트오더는 위와 같다.

규칙을 발견해보자.

1. 포스트오더의 맨 끝은 루트 노드가 된다.
2. 포스트오더를 통해 발견된 루트 노드의 값을 가지고 인오더에서 그 노드번호를 찾으면
3. 인오더는 그 루트 노드의 번호를 중심으로 왼쪽과 오른쪽 트리를 나눠준다.

또한 한 가지의 규칙이 더 발견된다.

바로 루트 노트와 연결된 왼쪽 자식 노드의 번호와 오른쪽 자식 노드의 번호이다.
이를 배열에 저장한다.

그리고 마지막에 재귀함수는 아래와 같이 다시 호출된다.

왼쪽 트리에 대한 재귀함수 호출

오른쪽 트리에 대한 재귀함수 호출


문제는 여기서 정말 배열로 재귀함수를 통해 전달한다면
메모리 초과가 발생한다!

n은 최대 100,000이기 때문에 왼쪽 트리와 오른쪽 트리를 나누는 과정에서 계속 새로운 배열을 만들어야 하기 때문이다.

따라서 트리를 나눌 때 배열을 전달하는 것이 아니라 index의 번호를 전달하도록 한다.


또한 이 문제에서 고려해야하는 것은

왼쪽에만 트리가 있는 경우

오른쪽에만 트리가 있는 경우

풀이(java)

import java.util.*;
import java.io.*;

public class Main {

    static int root;

    static int[][] arr;
    static int[] in;
    static int[] post;

    static StringBuilder answer = new StringBuilder();

   public static void main(String[] args) throws IOException {

       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

       int n = Integer.parseInt(br.readLine());//1부터 100_000
       in = new int[n];
       post = new int[n];

       arr =new int[n+1][2];

       StringTokenizer st = new StringTokenizer(br.readLine()," ");
       for(int i=0;i<n;i++){
           in[i] = Integer.parseInt(st.nextToken());
       }

       st = new StringTokenizer(br.readLine()," ");
       for(int i=0;i<n;i++){
           post[i] = Integer.parseInt(st.nextToken());
       }

       root = post[n-1];
       preOrder(0,in.length-1,0,post.length-1);


       make_arr(arr,root);

       System.out.println(answer);

   }

   static void preOrder(int in_start, int in_end,int post_start, int post_end){

       if(in_start>=in_end) return;

       int root_m = post[post_end];

       int in_root = 0;
       for(int i=in_start;i<=in_end;i++){
           if(in[i]==root_m){
               in_root=i;
               break;
           }
       }

       //left
       if(in_root != in_start) arr[root_m][0] = post[post_end-(in_end-in_root+1)];

       //right
       if(in_root!=in_end) arr[root_m][1]=post[post_end-1];

       //left
       if(in_root !=in_start)
           preOrder(in_start,in_root-1,post_start,post_end-(in_end-in_root+1));

       //right
       if(in_root!=in_end)
           preOrder(in_root+1,in_end,post_end-(in_end-in_root+1)+1,post_end-1);

   }

   static void make_arr(int[][] arr, int root){
      if(root==0) return;

       answer.append(root+" ");
       make_arr(arr,arr[root][0]);
       make_arr(arr,arr[root][1]);

   }



}
profile
꾸준하게 Ready, Set, Go!

0개의 댓글