[JAVA] 백준 트리 뿌수기3

 

 

이전글

https://fladi.tistory.com/405

[JAVA] 백준 트리 뿌수기1

https://fladi.tistory.com/406

[JAVA] 백준 트리 뿌수기2

 

 

트리부수기 시즌3이다!

 

 

 

 

 

 

5052 전화번호 목록 - 골드4

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

5052번: 전화번호 목록

• 이건 트리문제가 아니라는 걸 알고 풀었다면 더 재밌었을텐데 아쉽다
• 접두어가 되지 않으려면 해당 전화번호로 트리를 만드는 과정에서 리프노드를 만나면 안된다
  • 즉, 트리가 만들어질 때 리프노드가 아닌 쪽으로 가지가 뻗어나가야함
• 일단 번호 하나로 트리를 만들고, 다른 번호로 트리 가지를 뻗어나갈 때, 분기점이 리프노드가 되지 않는지 검사하면 되겠다

 

class Node {
    int num;
    List<Node> children;
    boolean isLeaf;

    public Node(int num, List<Node> children, boolean isLeaf) {
        this.num = num;
        this.children = children;
        this.isLeaf = isLeaf;
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tcCnt = Integer.parseInt(br.readLine());
        for (int tc =0; tc<tcCnt; tc++) {
            int telCnt = Integer.parseInt(br.readLine());

            Node root = new Node(-1, new ArrayList<>(), false);
            boolean isGood = true;

            for (int i =0; i<telCnt; i++) {
                String input = br.readLine();
                Node prev = root;

                if (!isGood) {
                    continue;
                }

                for (int j =0; j<input.length(); j++) {
                    int num = Character.getNumericValue(input.charAt(j));

                    if (prev.isLeaf) {
                        isGood = false;
                        continue;
                    }

                    boolean find = false;
                    for (Node child: prev.children) {
                        if (child.num == num) {
                            find = true;
                            prev = child;
                            break;
                        }
                    }

                    if (find) {
                        if (prev.isLeaf) {
                            isGood = false;
                        }

                        if (j == input.length()-1) {
                            isGood = false;
                        }
                    } else  {
                        Node newNode;
                        if (j == input.length()-1) {
                            newNode = new Node(num, new ArrayList<>(), true);
                        } else {
                            newNode = new Node(num, new ArrayList<>(), false);
                        }
                        prev.children.add(newNode);
                        prev = newNode;
                    }
                }
            }

            if (isGood) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
    }
}

• 이렇게 풀 때 주의점이 있다
• 11923이 나온 후 119가 나올 때도 일관성이 없다고 체크를 해줘야한다.
• 분명히 정석 풀이가 있을 것 같아 다른 풀이도 찾아봤다

 

 

다른풀이

1. 문자열 활용: 정렬 + startsWith 메소드를 사용하기
   • 굳이 트리를 안만들어도 되는 방법! 문자열을 활용하는 방법이다
   • 시간을 줄이기 위해 정렬도 필수다
   • 대부분 사람들이 이 풀이로 풀었다(정석인듯)
   • 참고자료: https://moonsbeen.tistory.com/76
   • https://steady-coding.tistory.com/78
2. 트라이 사용
   • 트라이는 처음 들어보는 자료구조다 (다음에 공부해봐야지)
   • 종료지점을 저장하여 접두사가 있는지 확인하는 것 같다. 이 문제와 정말 잘어울리는 자료구조인 듯 하다.
   • 참고자료: https://loosie.tistory.com/447
3. map을 사용하여 하나하나 비교하기
   • 정렬 후 map에 넣으면서 map내부의 값과 비교한다
   • 112라면 1, 11, 112를 map에서 다 찾는다
   • map이라서 은근 시간이 많이 안들 것 같다. startWith랑 비슷할듯
   • 꽤 재밌는 풀이다!
   • 참고: https://dingdingmin-back-end-developer.tistory.com/entry/%EB%B0%B1%EC%A4%80-5052%EC%9E%90%EB%B0%94-java-%EC%A0%84%ED%99%94%EB%B2%88%ED%98%B8-%EB%AA%A9%EB%A1%9D

 

구글 상단 10개의 풀이를 찾아봤는데 대부분 사람들이 1, 2번째 풀이로 풀었고 트리를 사용하신 분은 못봤다.

트리는 일반적인 풀이가 아닌가보다. (트라이라는 좋은 자료구조가 있으니 그럴만도 하다)

 

 

 

 

9489 사촌 - 골드4

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

9489번: 사촌

• 연속수열로 트리를 만든 후
• 할머니의 다른 자식들의 자식들을 카운트하면 될듯..
• 트리를 직접 만들었더니 시간초과가 나서 다른풀이의 아이디어를 조금 참고하여 문제를 풀었다.

 

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

        StringBuilder sb = new StringBuilder();
        while (true) {
            StringTokenizer st=  new StringTokenizer(br.readLine());
            int nodeCnt = Integer.parseInt(st.nextToken());
            int num = Integer.parseInt(st.nextToken());

            if (nodeCnt == 0 && num == 0) {
                break;
            }

            String input = br.readLine();

            sb.append(solution(nodeCnt, num, input) + "\n");
        }

        System.out.print(sb);
    }

    private static int solution(int nodeCnt, int num, String input) {
        StringTokenizer st = new StringTokenizer(input);
        int prev = 0;

        int[] values = new int[nodeCnt];
        int[] parentIdxArr = new int[nodeCnt];

        int numIdx=  0;
        for (int i =0; i<nodeCnt; i++) {
            values[i] = Integer.parseInt(st.nextToken());
            if (values[i] == num) {
                numIdx = i;
            }
        }

        int parentIdx = 0;
        for (int i =1; i<values.length; i++) {
            int current = values[i];

            if (prev == 0) {
                prev = current;
                parentIdxArr[i] = parentIdx;
                continue;
            }

            if (prev+1 == values[i]) {
                parentIdxArr[i] = parentIdx;
            } else {
                parentIdx++;
                parentIdxArr[i] = parentIdx;
            }

            prev = current;
        }

        parentIdxArr[0] = -1;

        int currentParentIdx = parentIdxArr[numIdx];
        if (currentParentIdx == -1) {
            return 0;
        }
        int currentGrandmaIdx = parentIdxArr[currentParentIdx];
        if (currentGrandmaIdx == -1) {
            return 0;
        }

        int cousinCnt  =0;
        int sisterCnt = 0;

        for (int i =1; i<parentIdxArr.length; i++) {
            int p = parentIdxArr[i];
            if (p == currentGrandmaIdx) { //i는 이모
                for (int j =1; j<parentIdxArr.length; j++) {
                    int p2 = parentIdxArr[j];
                    if (p2 == i) {//j는 이모의 딸
                        cousinCnt++;
                    }
                }
            } else if (p == currentParentIdx) {
                sisterCnt++;
            }
        }

        return cousinCnt - sisterCnt;
    }
}

• 순서대로 배열되는 건 굳이 PriorityQueue에 넣지 않아도 순서대로 들어와서 그대로 넣으면 된다
  • 부모가 자식보다 크다는 조건이 있기 때문
• 부모의 인덱스를 저장하는 배열을 만들고, 배열에서 해당 부모를 가지는 노드를 찾는 방법을 사용했다
• 좋은 풀이는 아닌 것 같아 다른 풀이를 찾아봤다

 

 

다른풀이

1. 부모의 인덱스를 저장하는 parent배열을 만들고, parent의 parent가 parent의 parent와 같은 걸 찾기
   • 내가 참고한 풀이지만 내 풀이보다 더 깔끔하다(왜 생각못했을까)
   • 인덱스를 사용했다면 parent의 parent를 바로 구할 수 있기 때문에 바로 비교할 수 있다
   • 대부분이 이 방식으로 푼 것 같다. 정석풀이인듯
   • 내가 참고한 블로그: https://loosie.tistory.com/608
   • 다른 블로그: https://codingjerk-diary.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%ED%92%80%EC%9D%B4%EB%B0%B1%EC%A4%80-9489-%EC%82%AC%EC%B4%8C-JAVA

 

큐 방식을 이용하는 풀이도 있었는데 코드가 읽기 힘들어 스킵한다.

남의 코드를 보는건 쉬운 일이 아닌 것 같다. (챗지피티를 잘 쓰는 친구가 존경스럽다)

 

 

 

 

14267 회사 문화 1 - 골드4

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

14267번: 회사 문화 1

• 각각 노드에서 루트까지 가면서 칭찬을 저장하기엔 시간초과가 날 것 같다
• 부모를 저장하기보단, 자식을 저장하는 자료구조를 만들고, 각각 직원이 칭찬받은 수치를 저장할 배열도 추가하면 좋을 것 같다.
  • 그리고 칭찬수치를 아래까지 전염시키면 좋을듯
  • 시간초과가 났다
• 스캔횟수를 줄이기 위해 일단 칭찬수치를 다 저장해두고 마지막에 루트부터 삭 돌면서 전파시키는 방법을 사용했다

 

public class Main {
    static ArrayList<Integer>[] children;
    static int[] compliments;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int staffCnt = Integer.parseInt(st.nextToken());
        int complimentCnt = Integer.parseInt(st.nextToken());

        children = new ArrayList[staffCnt];
        for (int i=0; i<children.length; i++) {
            children[i] = new ArrayList<>();
        }

        st = new StringTokenizer(br.readLine());
        st.nextToken(); //루트노드 제외
        for (int i =1; i<staffCnt; i++) {
            int parent = Integer.parseInt(st.nextToken())-1;
            children[parent].add(i);
        }

        compliments = new int[staffCnt];

        for (int i =0; i<complimentCnt; i++) {
            st = new StringTokenizer(br.readLine());
            int staffNum = Integer.parseInt(st.nextToken())-1;
            int amount = Integer.parseInt(st.nextToken());
            compliments[staffNum] += amount;
        }

        spreadCompliment(0, 0);

        StringBuilder sb = new StringBuilder();
        for (int i=0; i<compliments.length; i++) {
            sb.append(compliments[i] + " ");
        }

        System.out.println(sb);
    }

    private static void spreadCompliment(int num, int amount) {
        compliments[num] += amount;
        for (int child: children[num]) {
            spreadCompliment(child, compliments[num]);
        }
    }
}

• 자식을 저장하는 방식으로 바꿔서 편하게 전파시켰다
• (트리문제는 다익스트라와 달리 풀이가 다 제각각이라서 감잡는게 쉽지않은 것 같다. 실력은 늘고있길 바라고있음)

 

 

 

 

20924 트리의 기둥과 가지 - 골드4

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

20924번: 트리의 기둥과 가지

• 나무그림 설명이 굉장히 웃기다
• 기둥의 길이는 루트 ~ 기가노드까지 -> 자식이 하나인 애들 개수를 세면서 길이를 계산하면 될듯
  • 부모제외, 자식이 하나만 있으면 재귀호출 해주고
  • 부모제외, 자식이 하나가 아니면 기가노드로 판단하고 return하는 식으로 구상했다
• 기가노드부터 리프까지 가장 긴 길이는 dfs로 구하면 되겠다

 

class Node {
    int end;
    int value;

    public Node(int end, int value) {
        this.end = end;
        this.value = value;
    }
}

public class Main {
    static ArrayList<Node>[] arr;
    static int rootNum;
    static int pillarLength = 0;
    static int longestBranchLength = 0;
    static boolean[] visit;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int nodeCnt = Integer.parseInt(st.nextToken());
        rootNum = Integer.parseInt(st.nextToken())-1;

        arr = new ArrayList[nodeCnt];
        for (int i =0; i<arr.length; i++) {
            arr[i] = new ArrayList<>();
        }

        for (int i =0; i<nodeCnt-1; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken())-1;
            int b = Integer.parseInt(st.nextToken())-1;
            int distance = Integer.parseInt(st.nextToken());
            arr[a].add(new Node(b, distance));
            arr[b].add(new Node(a, distance));
        }

        visit = new boolean[nodeCnt];

        int giga = findGiga(rootNum, rootNum, 0);
        dfs(giga, giga, 0);

        System.out.println(pillarLength + " " + longestBranchLength);
    }
    
    private static void dfs(int node, int parent, int sum) {
        int count = 0;
        for (Node child: arr[node]) {
            if (parent != child.end && !visit[child.end]) {
                dfs(child.end, node, sum + child.value);
                count++;
            }
        }

        if (count == 0) {
            if (longestBranchLength < sum) {
                longestBranchLength = sum;
            }
        }
    }

    private static int findGiga(int node, int parent, int sum) {
        List<Node> children = new ArrayList<>();
        for (Node child: arr[node]) {
            if (parent != child.end) {
                children.add(child);
                if (children.size() >= 2)
                    break;
            }
        }

        if (children.size() == 1) {
            Node uniqueChild = children.get(0);
            visit[node] = true;
            return findGiga(uniqueChild.end, node, sum+uniqueChild.value);
        } else {
            pillarLength = sum;
            return node;
        }
    }
}

• 이 풀이의 한가지 주의점은 기둥에서 기가노드로 갈 때 부모를 제외하고 dfs해줘야한다는 것이다
• 부모를 따로 저장하거나, visit배열을 관리해야할 것 같다. 나는 그냥 visit배열을 사용했다
• 분명 더 좋은 풀이가 많을 것 같았는데, 찾아보니 visit 체크를 하는게 일반적인 풀이인 것 같다

1.  

 

 

 

 

20955 민서의 응급 수술 - 골드4

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

20955번: 민서의 응급 수술

• 일단 연결된 그래프를 dfs로 찾으며 visit를 체크한다
• 만약 사이클이 존재하면 해당 간선을 끊고 result ++ 해준다
• 모든 노드에 대해 수행하며 트리의 개수를 세준다
• 트리의 개수-1만큼 result에 더해주면 될듯

 

public class Main {
    static ArrayList<Integer>[] arr;
    static boolean[] visit;
    static int calculateCnt = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int nodeCnt  = Integer.parseInt(st.nextToken());
        int synapseCnt = Integer.parseInt(st.nextToken());

        visit = new boolean[nodeCnt];
        arr = new ArrayList[nodeCnt];
        for (int i =0; i<arr.length; i++) {
            arr[i] = new ArrayList<>();
        }

        for (int i =0; i<synapseCnt; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken())-1;
            int b = Integer.parseInt(st.nextToken())-1;
            arr[a].add(b);
            arr[b].add(a);
        }

        int treeCnt = 0;
        for (int i =0; i<arr.length; i++) {
            if (!visit[i]) {
                dfs(i, i);
                treeCnt++;
            }
        }

        System.out.println(calculateCnt/2 + treeCnt-1);
    }

    private static void dfs(int node, int prev) {
        visit[node] = true;

        for (Integer adj: arr[node]) {
            if (prev != adj) {
                if (visit[adj]) {
                    calculateCnt++;
                } else {
                    dfs(adj, node);
                }
            }
        }
    }
}

• 사이클이 생기는 간선은 두 노드에서 중복될 수 있기 때문에 dfs로 연산횟수를 구한 후 2로 나눠줘야한다
• 이것만 주의하면 어려운 건 없다

 

 

 

 

22856 트리 순회 - 골드4

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

22856번: 트리 순회

• 그냥 중위순회를 하되, 노드에 들르는 횟수를 카운트 해주면 될 것 같다

 

class Node {
    int num;
    int left;
    int right;

    public Node(int num, int left, int right) {
        this.num = num;
        this.left = left;
        this.right = right;
    }
}

public class Main {
    static Map<Integer, Node> map = new HashMap<>();
    static int visitNum =0;
    static final int rootNum = 1;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int nodeCnt = Integer.parseInt(br.readLine());

        for (int i =0; i<nodeCnt; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int num = Integer.parseInt(st.nextToken());
            int left = Integer.parseInt(st.nextToken());
            int right = Integer.parseInt(st.nextToken());
            map.put(num, new Node(num, left, right));
        }

        //뺄 거 계산 - 트리 오른쪽을 쭉 타고 내려가면 됨
        int diff = 0;
        int endNum = rootNum;
        while (true) {
            Node node = map.get(endNum);
            if (node.right == -1) {
                break;
            } else {
                diff ++;
                endNum = node.right;
            }
        }

        //유사중위순회 수행, visitNum에 방문한 노드 모두저장
        simmilarInOrder(rootNum);
        System.out.println(visitNum - diff-1);
    }

    private static void simmilarInOrder(int num) {
        Node node = map.get(num);
        visitNum++;

        if (node.left != -1) {
            simmilarInOrder(node.left);
            visitNum++;
        }

        if (node.right != -1) {
            simmilarInOrder(node.right);
            visitNum++;
        }
    }
}

• 하나 주의해야할 점은 중위순회 끝 노드에서 루트까지 돌아오지 않는다는 거다
• 나는 유사중위순회로 방문한 노드 개수를 모두 센 후, 빼야하는 것만 빼주는 방법을 사용했다
  • 빼야하는 거: 오른쪽을 타고 쭉 내려가는 노드들 개수

 

 

 

 

2533 사회망 서비스(SNS) - 골드3

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

2533번: 사회망 서비스(SNS)

• dp를 사용해야할 것 같다
  • 각 depth마다 노드의 개수를 저장한 후, depth를 선택했을 때 = max(부모가 어답터일 때, 부모가 어답터가 아닐 때(할머니 어답터)) 이런식으로 구하면 될 것 같다
  • 루트가 주어지지 않기 때문에 임의의 한 점을 잡고 dfs쳐야할 것 같음 
  • 결과는 시간초과
• dp로 풀어야될 걸 알지만 dp실력이 부족한 것 같다. dp를 먼저 부수고 트리를 할껄 그랬다
• 다른 블로그의 풀이아이디어를 참고하여 문제를 풀었다
  • 자식부터 올라가면서 dp로 풀면 된다
  • 내가 얼리어답터일때, 내가 얼리어답터가 아닐 때 자식의 결과를 이용하면 쉽게 풀 수 있다
  • 아이디어 참고 블로그: https://maivve.tistory.com/322

 

public class Main {
    static ArrayList<Integer>[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int nodeCnt  =Integer.parseInt(br.readLine());

        arr = new ArrayList[nodeCnt];
        for (int i =0; i<arr.length; i++) {
            arr[i] = new ArrayList<>();
        }

        for (int i =0; i<nodeCnt-1; i++) {
            StringTokenizer st=  new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken())-1;
            int b = Integer.parseInt(st.nextToken())-1;
            arr[a].add(b);
            arr[b].add(a);
        }

        int[] pickMe = dfs(0,0);

        System.out.println(Math.min(pickMe[0], pickMe[1]));
    }

    private static int[] dfs(int node, int parent) {
        int cnt = 0;

        int[] current = new int[2];
        for (int child: arr[node]) {
            if (parent != child) {
                cnt++;
                int[] childResult = dfs(child, node);
                current[0] += childResult[0]; //자식을 무조건 뽑을경우
                current[1] += Math.min(childResult[0], childResult[1]); //자식 안뽑아도 될 경우(뽑아도 됨)
            }
        }

        if (cnt == 0) { //리프노드
            return new int[]{1, 0}; //나 뽑을 때, 나 안뽑을 때
        }

        return new int[]{1+current[1], current[0]};  //나 뽑을 때, 나 안뽑을 때
    }
}

• 아이디어만 생각하면 어렵지 않은데 아이디어가 절대 안떠오른다.. dp실력이 아직 부족한듯
• 아무 점이나 루트라고 생각하고 dfs를 수행한다. 나는 0을 점으로 지정해줬다
• dfs중 리프노드를 만나면 int배열을 반환한다. 
  • [0]은 나를 무조건 뽑을 때 값(=1)이고
  • [1]은 나를 안뽑아도 될 때 값(=0)이다
• 리프노드가 아니라면 자식에 대해 dfs를 수행한다
  • current[0]은 직속자식을 무조건 뽑을 경우 어답터의 개수이다. 자식의 반환배열 [0]을 더해주면 됨
  • current[1]은 직속자식을 안뽑아도 될 경우 어답터의 개수이다. 안뽑아도 되지만 뽑아도 되기 때문에 자식의 반환배열 중 작은 값을 더해준다
• 그리고 마지막에 나를 무조건 뽑을 때 값, 나를 안뽑아도 될 때 값을 반환한다
  • 나를 무조건 뽑을 때 = 자식 뽑아도되고 안뽑아도 됨 = current[1] + 1
  • 나를 안뽑아도 될 때 = 자식을 무조건 뽑아야함 = current[0]

 

 

 

더 좋은 풀이가 있을 것 같아 다른 풀이도 찾아봤다

1. 내가 참고한 블로그: dfs와 dp사용
   • 이 분은 반환값에 담지않고 dp배열을 만들었다(정석인듯)
   • 이분도 임의의 지점인 1부터 dfs를 시작했다. 자식먼저 dfs를 호출하여 dp배열을 채운 후, 해당 배열값을 이용하여 현재 노드의 배열값을 채우는 방식을 사용했다
   • 코드가 나보다 더 간결하고 이해하기 쉬워보인다
   • https://maivve.tistory.com/322

놀라운게 구글상위 10개이상의 블로그가 모두 위와 같은 방식으로 풀었다. dp느낌이 심하게 나서 모두 비슷한 방식으로 풀었나보다. 정석풀이인듯

 

 

 

 

6597 트리 복구 - 골드3

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

6597번: 트리 복구

• 전위순회 결과에서 루트노드도 알 수 있고 트리모양도 알 수 있을 것 같다. 
• 트리를 구성하고 이를 포스트오더로 순환하면 될 것 같다.

 

class Node {
    char num;
    Node left;
    Node right;

    public Node(char num, Node left, Node right) {
        this.num = num;
        this.left = left;
        this.right = right;
    }
}

public class Main {
    static String preOrder; //루트찾기용
    static String inOrder; //반자르기용

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

        try {
            while (true) {
                String input = br.readLine();
                if (input.split(" ").length <= 1 || input.length() == 0) {
                    break;
                }

                StringTokenizer st = new StringTokenizer(input);
                preOrder = st.nextToken(); //루트찾기용
                inOrder = st.nextToken(); //왼 루트 오

                Node root = makeTree(0, preOrder.length() - 1, 0, inOrder.length() - 1);
                postOrder(root);
                System.out.println();
            }
        } catch (Exception e) {

        }
    }

    private static void postOrder(Node node) {
        if (node.left != null)
            postOrder(node.left);

        if (node.right != null)
            postOrder(node.right);

        System.out.print(node.num);
    }

    private static Node makeTree(int startPre, int endPre, int startIn, int endIn) {
        if (startPre == endPre) {
            return new Node(preOrder.charAt(startPre), null, null);
        }

        char rootChar = preOrder.charAt(startPre);
        int mid = 0;

        for (int i =startIn; i<=endIn; i++) {
            if (rootChar == inOrder.charAt(i)) {
                mid = i;
                break;
            }
        }

        Node leftNode = null;
        if (startIn != mid) {
            int diff = (mid -1 - startIn);
            leftNode = makeTree(startPre+1, startPre+1 + diff, startIn, mid-1);
        }

        Node rightNode = null;
        if (endIn != mid) {
            int diff = (endIn - (mid+1));
            rightNode = makeTree(endPre - diff, endPre, mid+1, endIn);
        }

        return new Node(
                inOrder.charAt(mid),
                leftNode,
                rightNode
        );
    }
}

• 입력이 익숙하지 않아서 NullPointerError가 계속 났다.. 결국 하루를 썼는데 시간이 너무 아까움. 다음엔 꼭 catch를 써야겠다
• 그냥 반씩 자르면서 트리를 구성하면 된다
• 입력문제 때문에 다른 풀이를 찾아봤는데 좋은 풀이가 많은 것 같아 더 찾아봤다

 

다른풀이

1. inOrder의 left right를 넣고 preOrder에 있는 루트노드 인덱스를 이용하기
   • recover(idx, left, right) 로 재귀호출을 수행한다
   • left와 right는 inOrder 기준이고, idx는 preOrder기준 인덱스다
   • 왼쪽노드의 루트는 idx+1이고, 오른쪽 노드의 루트는 왼쪽노드들을 다 재꾼 (idx + 1 + roodIdx - left)로 구한다
   • 이렇게 구하는 게 훨씬 가독성이 좋아보인다! 좋은풀이!
   • https://loosie.tistory.com/609
2. subString을 사용한 풀이
   • 나는 preOrder와 inOrder의 start, end 인덱스를 사용하였고 이 풀이는 subString을 사용하셨다
   • 왼쪽 서브트리 크기, 오른쪽 서브트리 크기를 이용하여 인덱스를 깔끔하게 나누셨다
   • c++풀이지만 가독성이 좋아서 한 번 봐두면 좋을 것 같다
   • https://jaimemin.tistory.com/1159
3. preOrder순서로 순회하면서 바로 postOrder를 출력 👍👍
   • 전위, 중위, 후위순회에 대한 이해도가 높으신 것 같다
   • 중위 후위순회와 첫 번째 노드는 같으므로, 일단 왼쪽으로 타고들어간다
   • 이후 오른쪽노드부터 타고들어가면서 출력하여 바로 postOrder를 출력하셨다
   • 참신해서 한 번 봐두면 큰 도움이 될 것 같다. 좋은풀이!
   • https://rccode.tistory.com/253

 

 

 

 

7432 디스크 트리 - 골드3

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

7432번: 디스크 트리

• 안타까운 상근이 이야기다(다시 켜져서 다행)
• 디렉토리는 트리구조이기 때문에 트리를 구성하면 되겠다
• 역슬래시로 split하고 트리에 매달아주면 되겠다

 

public class Main {
    static TreeMap<String, TreeMap> map = new TreeMap<>(new Comparator<String>() {
        @Override
        public int compare(String o1, String o2) {
            return o1.compareTo(o2);
        }
    });
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int routeCnt = Integer.parseInt(br.readLine());

        for (int i =0; i<routeCnt; i++) {
            String input = br.readLine();
            String[] arr = input.split("\\\\");
            Map<String, TreeMap> tmp = map;

            for (int j =0; j<arr.length; j++) {
                String fileName = arr[j];

                if (tmp.get(fileName) == null) {
                    TreeMap<String, TreeMap> children = new TreeMap<>();
                    tmp.put(fileName, children);
                    tmp = children;
                } else {
                    tmp = tmp.get(fileName);
                }
            }
        }

        for (String key: map.keySet()) {
            print(key, map.get(key), 0);
        }
    }

    private static void print(String key, TreeMap<String, TreeMap> children, int depth) {
        System.out.println((" ".repeat(depth)) +key);

        if (children == null) {
            return;
        }
        for (String k: children.keySet()) {
            print(k, children.get(k), depth+1);
        }
    }
}

• 실수로 TreeMap 내부의 TreeMap에는 Comparator를 설정안해줬는데 통과됐다
  • 설정 안해줘도 알아서 문자열로 정렬되나보다.. 몰랐다
• TreeMap 외에는 어려울 건 없는 문제같다

 

 

 

 

11437 LCA - 골드3

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

11437번: LCA

• 이전에도 본 가장 가까운 공통조상 문제다(3584)
• 타고 올라가면서 체크하는 기억이 난다. 한 번 그 방법으로 풀어봐야지

 

public class Main {
    static ArrayList<Integer>[] arr;
    static int[] parent;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int nodeCnt = Integer.parseInt(br.readLine());

        parent = new int[nodeCnt];

        arr = new ArrayList[nodeCnt];
        for (int i =0; i<arr.length; i++) {
            arr[i] = new ArrayList<>();
        }

        for (int i=0; i<nodeCnt-1; i++) {
            StringTokenizer st= new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken())-1;
            int b = Integer.parseInt(st.nextToken())-1;

            arr[a].add(b);
            arr[b].add(a);
        }

        parent[0] = -1;
        makeParent(0, 0);

        int pairCnt = Integer.parseInt(br.readLine());
        for (int i=0; i<pairCnt; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken())-1;
            int b = Integer.parseInt(st.nextToken())-1;

            boolean[] visit = new boolean[nodeCnt];
            while (a != -1) {
                visit[a] = true;
                a = parent[a];
            }

            while (!visit[b]) {
                b = parent[b];
            }

            System.out.println(b+1);
        }
    }

    private static void makeParent(int node, int p) {
        for (Integer child: arr[node]) {
            if (p != child) {
                parent[child] = node;
                makeParent(child, node);
            }
        }
    }
}

• 시간초과가 날 것같이 채점속도가 느렸지만 풀리긴 했다
• 체크하면서 따라가는 방법을 사용했다
• 다른 풀이도 찾아봄

 

다른풀이

1. 루트노드부터 높이와 부모를 저장, 노드의 높이를 일정하게 맞춘 후 비교
   • 나는 무조건 루트까지 체크해줬는데, 높이를 맞추면서 비교하면 더 빠르게 구할 수 있어서 좋을 것 같다
   • 메모리는 약간 더 들어도 더 빠르게 구할 수 있을듯
   • https://loosie.tistory.com/360

 

대부분이 이 풀이로 풀었다. LCA라는 알고리즘 자체로 분류되어 대부분이 이 풀이로 푸는 걸 볼 수 있다

 

 

 

 

 

11812 K진 트리 - 골드3

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

11812번: K진 트리

• 트리를 직접 구성하려고 했는데, N이 10의 15승인 걸 보고 다른 규칙을 찾아야겠다고 생각했다.
• 혼자 해보려다 시간초과 폭탄맞고 풀이방법을 찾아봤다.
  • (사실 시간초과의 이유는 k가 1일 때 따로 처리를 안해줬기 때문이었음)
• 부모는 (n-2)/k + 1 이다
  • 증명: 1+k^0+k^1+k^2의 부모는  1+k^0+k^1 다. (자식 -2)/k + 1을 하면 부모를 만들 수 있음
  • 무조건 된다
• 깊이는 알아서 구하면 된다
  • 1+k^0+k^1 을 반복해보면서 범위를 찾으면 됨
• k=1일 때는 이렇게 구하면 시간초과가 나니 따로 처리해줘야한다

 

public class Main {
    static int k;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        st.nextToken(); //알 바 x
        k = Integer.parseInt(st.nextToken());
        int pairCnt = Integer.parseInt(st.nextToken());

        for (int i =0; i<pairCnt; i++) {
            st = new StringTokenizer(br.readLine());
            long a = Long.parseLong(st.nextToken());
            long b = Long.parseLong(st.nextToken());

            if (k == 1) {
                System.out.println(Math.abs(a-b));
                continue;
            }

            long distance = 0;

            long depthA = getDepth(a);
            long depthB = getDepth(b);

            if (depthA > depthB) {
                while (depthA != depthB) {
                    a = getParent(a, depthA);
                    depthA--;
                    distance++;
                }
            } else if (depthA < depthB) {
                while (depthA != depthB) {
                    b = getParent(b, depthB);
                    depthB--;
                    distance++;
                }
            }

            if (a == b) {
                System.out.println(distance);
            } else {
                while (a != b) {
                    a = getParent(a, depthA);
                    b = getParent(b, depthB);
                    depthA--; depthB--;
                    distance += 2;
                }
                System.out.println(distance);
            }
        }
    }

    private static long getParent(long n, long depth) {
        return (n-2)/k + 1;
    }

    private static long getDepth(long n) { //0부터 시작
        long depth = 1;
        long start = 2;
        while (true) {
            if (n < start) {
                return depth-1;
            } else {
                start += (long)Math.pow(k, depth);
                depth++;
            }
        }
    }
}

 

 

 

 

 

 

 

 

 

 

다음부수기 후보: 비트마스킹, 트라이, 구현