프로그래머스 길 찾기 게임(lvl3) 풀어보기

문제링크

https://school.programmers.co.kr/learn/courses/30/lessons/42892

프로그래머스

---

문제 핵심

 너무길다

---

알고리즘

1.문제에서 제시한 조건의 tree만들기

-y값이 클수록 위쪽

-y값이 같다면 x값으로 비교

2.전위순회하기

3.후위순회하기

---

코드

 

 public static int[][] solution(int[][] nodeinfo) {

        int[][] answer = new int[2][nodeinfo[0].length];

        int[][] tree = new int[nodeinfo.length][5];

        for (int i = 0; i < nodeinfo.length; i++) {

            tree[i][0] = nodeinfo[i][0];

            tree[i][1] = nodeinfo[i][1];

            tree[i][2] = i + 1;

            tree[i][3] = -1;

            tree[i][4] = -1;

        }

        Arrays.sort(tree, (a, b) -> Integer.compare(b[1], a[1]));

        for (int i = 1; i < tree.length; i++) {

            int current = 0;

            while (true) {

                int direction = tree[i][0] < tree[current][0] ? 3 : 4;

                if (tree[current][direction] == -1) {

                    tree[current][direction] = i;

                    break;

                }

                current = tree[current][direction];

            }

        }

        System.out.println(Arrays.deepToString(tree));

        List<Integer>first=new LinkedList<>();

        dfs(tree,0,first);

        System.out.println(first);

        answer[0]=first.stream().mapToInt(Integer::intValue).toArray();

        first=new LinkedList<>();

        dfs2(tree, 0, first);

        System.out.println(first);

        answer[1]=first.stream().mapToInt(Integer::intValue).toArray();

        System.out.println(Arrays.deepToString(answer));

        return answer;

    }

    public static  void dfs(int[][] tree,int index,List<Integer>first){

        System.out.println("*"+Arrays.toString(tree[index]));

        first.add(tree[index][2]);

        if(tree[index][3]!=-1){

            dfs(tree, tree[index][3],first);

        }

        if(tree[index][4]!=-1){

            dfs(tree, tree[index][4],first);

        }

    }

    public static  void dfs2(int[][] tree,int index,List<Integer>first){

        if(tree[index][3]!=-1){

            dfs2(tree, tree[index][3],first);

        }

        if(tree[index][4]!=-1){

            dfs2(tree, tree[index][4],first);

        }

        first.add(tree[index][2]);

    }

 

---

결과

---

gpt피드백

1. 알고리즘 평가

개선점

① BST가 한쪽으로 치우치면 O(N²)이 발생할 수 있음

② 재귀 DFS의 깊이 문제

트리가 한쪽으로 치우치면 DFS 재귀 깊이도 O(N)이 돼. Java에서는 입력 크기에 따라 StackOverflowError가 발생할 수 있어.

③ 정렬 기준 보완

현재 y값만 내림차순 정렬했는데, 같은 y값에서는 x값까지 정렬하면 처리 순서가 명확해져.

 

2. 코드 평가

① answer 배열 크기 수정

② LinkedList 대신 ArrayList

④ DFS 함수 중복 제거

 

---

후기

어려운 문제였다

gpt한테 힌트많이 받았다

문제 자체를 이해하는데 gpt 도움을 많이 받았다

전위순회는 늘쓰던 방식과 비슷해서 금방 했는데

후위 순회는 떄려 맞췄다 그냥 마지막에 넣어보자하고 

했는데 된거다