공부흔적

문제 링크

풀이 )

  전위, 중위, 후위 순회 시 구조를 보고 풀었다.

• 전위: root ( left ) ( right )
• 중위: ( left ) root ( right )
• 후위: ( left ) ( right ) root

  후위 순회 결과의 마지막이 root이고 이를 이용해서 중위 순회에서의 root 위치를 찾아 좌 우를 나눈다.

  중위 순회에서의 root 위치를 빠르게 찾기 위해 index를 저장하는 배열을 만들었다.

import java.io.*;

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static int[] inOrder;
    static int[] postOrder;

    static int[] index;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        String[] in;

        int n = Integer.parseInt(br.readLine());
        inOrder = new int[n+1];
        postOrder = new int[n+1];
        index = new int[n+1];

        in = br.readLine().split(" ");
        for(int i = 0; i < n; ++i){
            inOrder[i] = Integer.parseInt(in[i]);
            index[inOrder[i]] = i;
        }
        in = br.readLine().split(" ");
        for(int i = 0; i < n; ++i)
            postOrder[i] = Integer.parseInt(in[i]);
        preOrder(0, n-1, 0, n-1);
        bw.flush();
    }

    static void preOrder(int inSrt, int inEnd, int postSrt, int postEnd) throws IOException {
        if(inSrt > inEnd || postSrt > postEnd)
            return;

        int root = postOrder[postEnd];
        bw.write(root+" ");
        int idx = index[root];
        preOrder(inSrt, idx-1, postSrt, postSrt+(idx-1-inSrt));
        preOrder(idx+1, inEnd, postSrt+(idx-inSrt), postEnd-1);
    }
}

주의 )

  인덱스 실수

문제 링크

풀이 )

  set을 사용하여 더 빠르게 풀 수 있지만 트라이를 이용해서 풀었다.

  n번의 입력에 대해서 트라이를 생성한 이후

  m번의 입력에 대해서 트라이를 타고가면서 마지막까지 도달한다면 끝인지 확인하여 답을 늘려주었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] in = br.readLine().split(" ");

        int n = Integer.parseInt(in[0]), m = Integer.parseInt(in[1]);
        Node root = new Node();
        while(n-- > 0){
            String str = br.readLine();
            Node cur = root;
            for(int i = 0; i < str.length(); ++i){
                char c = str.charAt(i);
                if(cur.children[c-'a'] == null)
                    cur.children[c-'a'] = new Node();
                cur = cur.children[c-'a'];

                if(i == str.length()-1)
                    cur.isLast = true;
            }
        }

        int ans = 0;
        while(m-- > 0){
            String str = br.readLine();
            Node cur = root;
            for(int i = 0; i < str.length(); ++i){
                char c = str.charAt(i);
                if(cur.children[c-'a'] == null)
                    break;
                cur = cur.children[c-'a'];

                if(i == str.length()-1 && cur.isLast)
                    ans++;
            }
        }
        System.out.println(ans);
    }

    public static class Node{
        Node[] children = new Node[26];
        boolean isLast;

        public Node(){}
    }
}

문제 링크

풀이 )

  트라이라는 자료구조를 공부한 다음에 풀었다.

  트라이는 k진 트리의 구조를 띄고 있고, 접두어를 찾을 때 효율적인 자료구조이다.

  root 노드를 시작으로 입력받은 숫자를 한자리씩 노드에 추가한다.

  1번 예제에서는 root를 시작으로 911에 대해서 9를 root의 자식 노드로 추가하고 9의 자식에 1, 1의 자식에 1을 추가한 뒤 마지막 1에서 마지막이라는 것을 표시한다.

  97625999은 현재 root에 9가 있기 때문에 9로 이동하고, 이후에 7이 없기 때문에 노드를 추가한 후 이후에도 같은 방식으로 한다.

  마지막 91125426에 대해서는 root에서 9로 이동한 후 1 1을 따라가면 1에 마지막 표시가 있기 때문에 NO를 출력한다.

   root

/

9

|     \

1        7

|          |

1         6

|          |

2         2

|          |

5         5

|          |

4         9

|          |

2         9

|          |

6         9

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int t = Integer.parseInt(br.readLine());
        while(t-- > 0){
            Node root = new Node();

            boolean flag = false;
            int n = Integer.parseInt(br.readLine());
            while(n-- > 0){
                Node cur = root;
                char[] number = br.readLine().toCharArray();
                if(flag == true)
                    continue;
                for(int i = 0; i < number.length; ++i){
                    char num = number[i];
                    if(i == number.length-1)
                        if(cur.children[num-'0'] != null){
                            flag = true;
                            break;
                        }

                    if(cur.children[num-'0'] == null)
                        cur.children[num-'0'] = new Node();
                    cur = cur.children[num-'0'];

                    if(cur.isLast){
                        flag = true;
                        break;
                    }
                    if(i == number.length-1)
                        cur.isLast = true;
                }
            }
            if(flag)
                sb.append("NO\n");
            else
                sb.append("YES\n");
        }
        System.out.print(sb);
    }

    static class Node{
        Node[] children = new Node[10];
        boolean isLast;

        public Node() {}
    }
}

주의 )

  중간에 NO를 출력하기 위해 break를 했을 때 n번 입력받는 while을 탈출해서 런타임에러가 났었다.

  자주하는 실수라 기억해둬야할 것 같다.