자바는 원본 배열도 같이 정렬해서 줘야하나보다. 일단 위 내용 생각해서 푼건 아래와 같음

class Solution {
    public int removeDuplicates(int[] nums) {

        int prev = Integer.MAX_VALUE;
        int cnt = 0;

        for (int i=0; i<nums.length; i++) {
            int current = nums[i];
            if (prev == current) {
                if (cnt >= 2) {
                    nums[i] = Integer.MAX_VALUE;
                } else {
                    cnt++;
                }
            } else {
                prev = current;
                cnt = 1;
            }
        }

        Arrays.sort(nums);

        int k = 0;
        for (int i=0; i<nums.length; i++) {
            if (nums[i] == Integer.MAX_VALUE) {
                break;
            }
            k++;
        }
        return k;
    }
}

어거지로 푼 느낌이라서 솔루션 참고했다. 논리적으로 한 숫자는 at most twice이므로 투포인터로 찾을 수 있나봄

핵심은 right와 left - 2 인덱스의 비교인데, 최대 2번까지 이어질 수 있으므로 이게 다르다면

• left와 right는 2부터 시작, 처음 두 요소는 유효하다고 가정
• right는 left - 2와 비교
  • 같으면: 해당 요소가 세 번째 등장한다는 뜻이므로 무시해야 함
  • 다르면: 해당 요소가 결과에 포함될 수 있음

class Solution {
    public int removeDuplicates(int[] nums) {
        int left = 2;
        for (int right=2; right<nums.length; right++) {
            if (nums[right] != nums[left - 2]) {
                nums[left] = nums[right];
                left++;
            }
        }
        return left;
    }
}

문자열을 제시된 규칙에 따라 분해하는 문제다. 아래를 핵심으로 생각하고 풀었다.

• x에 대한 변수와, x값과 x가 아닌 값에 대한 카운트 변수 필요
• 초기화용 플래그 필요 -> 소문자로만 이루어졌다고 했으므로 '#'으로 초기화
• 초기값을 만났을 때는 x를 세팅하고 카운트 증가
• 그 외 x == s.charAt(i)면 x++, 아니면 nx++
• 카운트 증가시킨 뒤 정확히 일치하게 되는 순간 다시 초기화하고, answer++

이후 x에 대한 카운트와 nx에 대한 카운트가 다른 값이라면, 위 분해 기준으로 처리하지 못한 글자가 남아있다는 뜻이 된다. 그리고 그것은 하나의 문자열 덩어리로 취급되므로, answer++ 처리해주면 끝난다.

class Solution {
    public int solution(String s) {
        int answer = 0;

        char x = '#';
        int xCount = 0;
        int nxCount = 0;

        for (int i=0; i<s.length(); i++) {
            if (x == '#') {
                x = s.charAt(i);
                xCount++;
                continue;
            }

            if (s.charAt(i) == x) {
                xCount++;
            } else {
                nxCount++;
            }

            if (xCount == nxCount) {
                x = '#';
                xCount = 0;
                nxCount = 0;
                answer++;
            }
        }

        if (xCount != nxCount) {
            answer++;
        }
        return answer;
    }
}

허용된 알파벳, 불가능한 알파벳을 판별하기 위해 26 사이즈의 boolean 배열을 만들었다. skip을 돌면서 배열에 마킹을 해준다.

그 이후에 s의 각 캐릭터 별로 아래 행동을 해줌

• index만큼 이동할건데, 일단 +1해보고 알파벳 범위를 넘어가면 26으로 모듈러연산함. 그리고 이것이 사용 가능 알파벳이면 이동 카운트를 하나 증가시킴 (사용 가능한 알파벳이 아니면 카운트를 증가시키지 않고 스킵).
• 결과적으로 이동 카운트가 index 만큼 수행됨을 확인했으면 내가 원하는 알파벳으로 변환이 성공한 것이므로 정답 스트링에 추가함

import java.util.*;
class Solution {
    public String solution(String s, String skip, int index) {
        StringBuilder sb = new StringBuilder();

        boolean[] alpha = new boolean[26];
        Arrays.fill(alpha, true);

        for (char c : skip.toCharArray()) {
            alpha[c - 'a'] = false;
        }

        for (char c : s.toCharArray()) {
            int pos = c - 'a';
            int move = 0;

            while (move < index) {
                pos = (pos + 1) % 26;
                if (alpha[pos]) {
                    move++;
                }
            }

            sb.append((char) ('a' + pos));
        }

        return sb.toString();
    }
}

연속으로는 발음할 수 없고, 패턴에 따라서 달리 매칭될 수 있을 거로 생각해서 DFS로 풀었다.

그러면서 이거 왜 레벨 1짜리 문제지.. 하고 생각했는데 다른 사람 풀이 보니까 그냥 연속단어 뭉치 (예를 들면 "ayaaya")를 허용하지 않고 이후에 각 단어들을 치환해서 마지막에 isEmpty() 체크하더라..

똑똑하네..

class Solution {
    private String[] canSay = new String[] {
        "aya",
        "ye",
        "woo",
        "ma"
    };
    public int solution(String[] babbling) {
        int answer = 0;

        for (String b : babbling) {
            if (dfs(b, 0, -1)) {
                answer++;
            }
        }
        return answer;
    }

    private boolean dfs(String bab, int index, int prev) {
        if (index == bab.length()) {
            return true;
        }

        for (int i=0; i<canSay.length; i++) {
            if (i == prev) {
                continue;
            }

            String word = canSay[i];
            if (bab.startsWith(word, index)) {
                if (dfs(bab, index + word.length(), i)) {
                    return true;
                }
            }
        }
        return false;
    }
}

이건 뭐 문제에서 의사코드를 주니까 그대로 치면 정답인데.. 아무튼 이런 가로/세로 문제는 min, max값을 구해서 다른 편의 min, max와 비교하면 회전 상태까지 고려할 수 있다.

다른 사람들 풀이도 봤는데, min, max 함수를 따로 빼서 하는건 좋지만 while문 조건에 min(wallet), max(wallet)이 들어가게 되면 매번 평가할 것 같은데... 지갑은 안 변하기 때문에 나처럼 초기화하는게 맞다고 봄

class Solution {
    public int solution(int[] wallet, int[] bill) {
        int answer = 0;

        int walletMin = Math.min(wallet[0], wallet[1]);
        int walletMax = Math.max(wallet[0], wallet[1]);

        int min = Math.min(bill[0], bill[1]);
        int max = Math.max(bill[0], bill[1]);

        while (min > walletMin || max > walletMax) {
            if (bill[0] > bill[1]) {
                bill[0] /= 2;
            } else {
                bill[1] /= 2;
            }
            min = Math.min(bill[0], bill[1]);
            max = Math.max(bill[0], bill[1]);
            answer++;
        }

        return answer;
    }
}

사과를 가장 비싸게 팔 수 있는 경우는 최소값이 가장 높은 경우다. 그러므로 배열을 정렬해버리고, 앞에서 혹은 뒤에서 부터 팩사이즈(m)씩 끊어 계산한 뒤 누적하면 정답을 얻을 수 있다.

각 상자는 이미 정렬된 배열을 기반으로 만들어지므로 상자에서 가장 왼쪽에 있는 값이 p가 되고, 이 값만 뽑아서 m과 곱해준 값을 누적하면 된다.

참고로 기본 타입 배열이라서 리버스오더 쓰려면 별도 작업을 해야하므로 그냥 오름차순으로 하는게 낫다.

import java.util.*;
class Solution {
    public int solution(int k, int m, int[] score) {
        int answer = 0;
        Arrays.sort(score);

        for (int i=score.length - 1; i>=m - 1; i-=m) {
            answer += score[i - m + 1] * m;
        }

        return answer;
    }
}

마지막으로 롤러가 칠해진 포지션만 두면 쉽게 풀 수 있는 문제다.

Section 배열 모두 순회하면서 안 칠해진 포인트를 찾았다면 그걸 시작점으로 잡고 롤러 길이만큼 갱신하면 된다.

오름차순 기준이라 했으니 이 방법이 section[n]번째를 포함해서 오른쪽까지 가장 넓게 칠할 수 있는 방법이 되기 때문

class Solution {
    public int solution(int n, int m, int[] section) {
        int answer = 0;
        int end = 0;

        for (int s : section) {
            if (s > end) {
                answer++;
                end = s + m - 1;
            }
        }

        return answer;
    }
}

문제 구성만 보면 PriorityQueue 사용해서 어떻게든 풀 수 있는 것 같은데.. 비효율적이지만 일단 정확성만 생각하고 아래같이 풀어봤다.

class MedianFinder {

    PriorityQueue<Integer> pq;

    public MedianFinder() {
        pq = new PriorityQueue<>();
    }

    public void addNum(int num) {
        pq.offer(num);
    }

    public double findMedian() {
        int size = pq.size();

        int mid = size / 2;
        if (size % 2 == 0) {
            mid--;
        }

        List<Integer> temp = new ArrayList<>();

        int index = 0;
        while (!pq.isEmpty() && index < mid) {
            temp.add(pq.poll());
            index++;
        }

        double result;
        if (size % 2 == 0) {
            int m1 = pq.poll();
            int m2 = pq.poll();

            result = (m1 + m2) / 2.0;
            temp.add(m1);
            temp.add(m2);
        } else {
            int m = pq.poll();
            result = (double) m;
            temp.add(m); 
        }

        pq.addAll(temp);

        return result;
    }
}

당연히 테스트케이스가 커지면 문제가 생김.. 원본 PQ에 계속해서 연산 시도하고 있기 때문

그럼 좋은 아이디어가 뭐냐? 힙 두개를 이용해서 left, right를 구성하고, 각각은 Max Heap, Min Heap으로 구성한 뒤 peek() 하면 O(1)으로 해결할 수 있다. (물론 넣는 작업 자체는 O(log N)임)

이렇게 하기 위해서 addNum 작업 시 두 PQ에 균등하게 넣어주는게 중요하다. 왼쪽 (MaxHeap)을 우선으로 하고, 현재 num값이 left로 갈지 right로 갈지 peek()을 통해 판단한다.

이후 더 중요한건 리밸런싱인데, left 사이즈와 right 사이즈가 2이상 차이나면 서로에게서 poll한다음 옮겨준다.

모든 작업 시 고려해야 할 점은 left가 우선권이 있기 때문에 사이즈가 같거나, 혹은 right보다 1 더 클 수 있다는 점이다.

class MedianFinder {

    private PriorityQueue<Integer> left;
    private PriorityQueue<Integer> right;

    public MedianFinder() {
        left = new PriorityQueue<>((o1, o2) -> o2 - o1);
        right = new PriorityQueue<>((o1, o2) -> o1 - o2);
    }

    public void addNum(int num) {
        if (left.isEmpty() || left.peek() >= num) {
            left.offer(num);
        } else {
            right.offer(num);
        }

        if (left.size() > right.size() + 1) {
            right.offer(left.poll());
        } else if (right.size() > left.size()) {
            left.offer(right.poll());
        }
    }

    public double findMedian() {
        if (left.size() == right.size()) {
            return (left.peek() + right.peek()) / 2.0;
        }
        return left.peek();
    }
}

문제 종류가 Heap이고, 빈도 수가 가장 높은 k개의 숫자를 배열로 리턴하란다. 그럼 먼저 떠오른게 PriorityQueue인데, 문제는 뭘 기준으로 정렬하느냐다.

당연히 정렬은 빈도다. 근데 빈도는 아직 모른다. 그럼 빈도 먼저 O(n)으로 계산해서 맵에 넣어 두고, PriorityQueue의 정렬방식을 빈도 수 기준으로 내림차순 해주면 되겠다.

맵의 각 entry를 PriorityQueue에 넣고, 최종적으로는 k개만 꺼내서 정답 배열에 주면 된다.

문제에서 요구하는 시간복잡도가 O(n log n)인데,
빈도수 구하기 O(n)이고 이걸로 구해진 맵에다 힙 연산이므로 n log n 해서 결국 O(N log N)이다.

class Solution {
    public int[] topKFrequent(int[] nums, int k) {

        Map<Integer, Integer> map = new HashMap<>();
        for (int n : nums) {
            map.put(n, map.getOrDefault(n, 0) + 1);
        }

        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o2[1] - o1[1]);
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            pq.offer(new int[] { entry.getKey(), entry.getValue() });
        }

        int[] result = new int[k];
        for (int i=0; i<k; i++) {
            result[i] = pq.poll()[0];
        }

        return result;
    }
}

애초에 힙에 k개만 유지하도록 코딩하면 (size > k 일 때 poll) 힙 연산에 드는 비용을 더 줄일 수도 있다.

이전에 풀었던 문제 같은데, 간단하게 다시 정리할 수 있다.

각 lists 요소는 ListNode 형태로, 이미 오름차순 정렬된 리스트다. 그러므로 PriorityQueue(우선순위는 node.val 기준)를 사용해서 첫 노드들을 모두 담아준 뒤에, 이후에 큐를 순회하면서 바꿔줄 수 있다.

껍데기용 head를 만들고, 큐에서 뽑은 것들을 순서대로 이어 붙인뒤 마지막에 head.next를 리턴해주면 된다.

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {

        PriorityQueue<ListNode> que = new PriorityQueue<>((n1, n2) -> Integer.compare(n1.val, n2.val));

        ListNode head = new ListNode();
        ListNode current = head;

        for (ListNode node : lists) {
            if (node != null) {
                que.offer(node);
            }
        }

        while (!que.isEmpty()) {
            current.next = que.poll();
            current = current.next;

            if (current.next != null) {
                que.offer(current.next);
            }
        }

        return head.next;
    }
}

나중에

이것도 문제를 보면 기본적으로 Trie를 생각해야 할 것 같다. 마찬가지로 각 노드당 isEnd 플래그를 두어 끝 문자까지 탐색이 완전히 되었는지 본다.

기본 Trie 구현문제와 달리 이 문제에서 생각해야 할 것은 와일드 카드가 있다는 것이다. . 입력은 어떤 캐릭터와도 매치될 수 있다.

그러므로 search 메서드의 구현은 기본 Trie 구현과는 조금 달라야 한다.

기본 구현에서는 조건이 참인 경우 node 포인터를 계속 바꿔가면서 했다면, 이 문제는 와일드카드인 경우의 체이닝과 기본 문자일 때의 체이닝이 다르기 때문이다.

즉, . 캐릭터가 들어온 순간 해당 깊이의 모든 자식들을 순회 대상에 포함해야 한다. 그러므로 dfs 방식, 메서드 분리하여 재귀로 풀어낸다.

일반 캐릭터라면 기본과 같이 child의 캐릭터로 계속 이어 나가면 되고, .라면 모든 child에 대해 계속 이어나가면 된다.

class WordDictionary {

    private Node root;
    private static class Node {
        Map<Character, Node> child;
        boolean isEnd;
        public Node() {
            this.child = new HashMap<>();
        }
    }

    public WordDictionary() {
        root = new Node();
    }

    public void addWord(String word) {
        Node node = root;
        for (char c : word.toCharArray()) {
            node.child.putIfAbsent(c, new Node());
            node = node.child.get(c);
        }
        node.isEnd = true;
    }

    public boolean search(String word) {
        return dfs(root, word, 0);
    }

    private boolean dfs(Node node, String word, int i) {
        if (node == null) {
            return false;
        }
        if (i >= word.length()) {
            return node.isEnd;
        }

        char c = word.charAt(i);
        if (c == '.') {
            for (char k : node.child.keySet()) {
                if (dfs(node.child.get(k), word, i + 1)) {
                    return true;
                }
            }
            return false;
        } else {
            if (!node.child.containsKey(c)) {
                return false;
            }
            return dfs(node.child.get(c), word, i + 1);
        }
    }
}

음 이거 풀었던 문제네 https://velog.io/@potato_song/Trie-Medium-Implement-Trie-Prefix-Tree

LCA(Lowest Common Ancestor) 찾는 문제. 두 노드 간의 최저 공통 조상이란, 두 노드를 모두 자식으로 갖는 가장 깊은 조상을 의미한다(후손에는 자신도 포함할 수 있음).

핵심 아이디어

• root가 p보다 크고 q보다도 크다 ==> root는 BST상에서 왼쪽 서브트리로 깊어질 수 있다.

• root가 p보다 작고 q보다도 작다 ==> root는 BST상에서 오른쪽 서브트리로 깊어질 수 있다.

• 둘 다 아니라면, root는 p와 q사이에 존재하는 값이므로 root 자체가 최저 공통 조상이 될 수 있다.

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (p.val < root.val && q.val < root.val) {
            return lowestCommonAncestor(root.left, p, q);
        }
        if (root.val < p.val && root.val < q.val) {
            return lowestCommonAncestor(root.right, p, q);
        }
        return root;
    }
}

Binary search tree가 주어졌을 때 k번째로 작은 수를 찾는 문제다. 핵심은 중위 순회다.

Binary search tree 특성 상 중위 순회하면서 count를 증/감 시키면 이것이 몇 번째로 작은 값인지 판단할 수 있게 된다. (왼쪽 서브트리는 항상 더 작은 값, 오른쪽 서브트리는 항상 더 큰 값) 중위 순회 시 left를 먼저 다 돌고 나온 count가 현재 노드가 몇 번째로 큰 지 알 수 있는 지표

이 문제에서는 k번째라는 명확한 수가 주어졌으므로, cnt = k로 정해놓고 별도의 cnt를 순회마다 하나씩 빼면서 0이 될 때 k번째로 작은 수임을 증명할 수 있다.

class Solution {
    private int answer;
    private int cnt;

    public int kthSmallest(TreeNode root, int k) {
        cnt = k;
        inOrder(root);
        return answer;
    }

    private void inOrder(TreeNode node) {
        if (node == null) {
            return;
        }

        // left
        inOrder(node.left);

        // root
        cnt--;
        if (cnt == 0) {
            answer = node.val;
            return;
        }

        // right
        if (cnt > 0) {
            inOrder(node.right);
        }
    }
}

속도가 만족스럽게 안나와서 GPT한테 개선 요청했는데, 스택 기반으로 풀어준다. 아마 느린 재귀 기반이 느린 이유는 메서드 콜 오버헤드, 캐시 지역성, GC 문제??

가독성 면에서 재귀가 더 좋아보이긴 함..

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode cur = root;

        while (cur != null || !stack.isEmpty()) {
            // 1) 왼쪽 끝까지 내려가며 스택에 쌓음
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            // 2) 가장 왼쪽 노드를 pop → 방문(작은 값부터 방문됨)
            cur = stack.pop();
            if (--k == 0) {
                return cur.val;
            }
            // 3) 오른쪽 서브트리로 진행
            cur = cur.right;
        }

        // k가 유효하지 않은 경우(문제 조건상 보통 나오지 않음)
        throw new IllegalArgumentException("k is out of bounds");
    }
}

Binary Search Tree가 유효한지 검사하는 문제다. 이진 탐색 트리에서 왼쪽 서브트리의 모든 노드는 루트보다 작아야 하고, 오른쪽 서브트리의 모든 노드는 루트보다 커야 한다.

그러므로 재귀적으로 풀 때 min, max값을 갱신해가며 풀어주면 된다. 각 재귀마다 루트값을 기준으로 min, max를 결정하며, 끝 부분과 min/max 사이에 있는 값인지 검사하면 논리적으로 맞다.

class Solution {
    public boolean isValidBST(TreeNode root) {
        return check(root, null, null);
    }

    private boolean check(TreeNode node, Integer min, Integer max) {
        if (node == null) {
            return true;
        }

        if (min != null && min >= node.val) {
            return false;
        }
        if (max != null && max <= node.val) {
            return false;
        }

        return check(node.left, min, node.val) && check(node.right, node.val, max);
    }
}

핵심 아이디어는 전위 순회를 베이스로 루트를 선택하고, 그 루트를 기준으로 왼쪽 서브트리, 오른쪽 서브트리 순으로 순회하는 것

그래도 혼자 생각할 때 아이디어가 안 떠올라서 GPT 참고함 기본적으로는 preOrder로 순회하는데, 이것을 루트로 삼아 left, right를 서브트리를 구함

결론적으로 preOrder의 경우 배열 순서대로 루트가 되며, 각각의 inOrder는 이 루트값을 기준으로 왼쪽/오른쪽이 나뉘는 것.

이것을 구현하기 위해서는 preOrder에 대한 포인터와 inOrder에 대한 포인터는 따로 관리가 되어야 함.

이 때 GPT는 inOrder의 포인터를 직관적이고 쉽게 다루기 위해 별도 해시맵에 담는다. 이것으로 pre (root)를 찾고 그 값을 기반으로 inOrder 배열에서 그 값이 어느 인덱스에 존재하는 지 얻을 수 있다.

class Solution {
    private int preIdx; // preorder에서 현재 루트 위치(전역 포인터)
    private int[] preorder;
    private int[] inorder;
    private java.util.Map<Integer, Integer> inIndex; // 값 -> inorder 인덱스

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        this.inorder = inorder;
        this.preIdx = 0;

        // inorder 값 -> 인덱스 맵 구성 (O(N))
        inIndex = new java.util.HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inIndex.put(inorder[i], i);
        }

        // inorder 구간 [inL, inR] (포함 범위)에서 트리 구성
        return build(0, inorder.length - 1);
    }

    private TreeNode build(int inL, int inR) {
        // 중위 구간이 비었으면 서브트리 없음
        if (inL > inR) return null;

        // 전위에서 현재 루트를 꺼냄
        int rootVal = preorder[preIdx++];
        TreeNode root = new TreeNode(rootVal);

        // 중위에서 루트 위치 찾기
        int mid = inIndex.get(rootVal);

        // 왼쪽: [inL, mid - 1], 오른쪽: [mid + 1, inR]
        root.left = build(inL, mid - 1);
        root.right = build(mid + 1, inR);

        return root;
    }
}

root와 subRoot 두 개의 트리가 주어졌을 때, root 안에 subRoot 트리와 완전히 동일한 서브트리가 있는지 확인하는 문제다. (당연히 인스턴스가 같은게 아니라, 구조와 노드 값들이 똑같은 것)

트리가 이진 탐색 트리도 아니고, 노드 val 자체도 중복해서 들어갈 수 있다는 전제가 있기 때문에.. subRoot의 val와 같은 모든 노드들을 찾아서 리스트에 넣어놓고 일일이 비교하는 로직을 짰다.

정답이 나오기는 하는데, 성능 결과를 보니 최선은 아닌 것 같다.

class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {

        // subRoot의 값과 같은 값을 가지는 노드들이 여러 개 있을 수 있으므로, 다 찾는다.
        int rootValue = subRoot.val;
        List<TreeNode> roots = new ArrayList<>();
        Queue<TreeNode> que = new ArrayDeque<>();
        que.offer(root);

        while (!que.isEmpty()) {
            TreeNode node = que.poll();
            if (node.val == rootValue) {
                roots.add(node);
            }

            if (node.left != null) {
                que.offer(node.left);
            }
            if (node.right != null) {
                que.offer(node.right);
            }
        }

        for (TreeNode node : roots) {
            if (dfs(node, subRoot)) {
                return true;
            }
        }

        return false;
    }

    private boolean dfs(TreeNode node, TreeNode subRoot) {
        if (node == null && subRoot == null) {
            return true;
        }
        if (node == null || subRoot == null) {
            return false;
        }
        if (node.val != subRoot.val) {
            return false;
        }

        return dfs(node.left, subRoot.left) && dfs(node.right, subRoot.right);
    }
}

그래서 개선하자면, 굳이 첫 while에서 모든 가능 후보들을 다 넣어놓고 추후에 돌리면서 판단할 필요 없이 즉시 즉시 같은 트리인지 판단하는게 반복 횟수를 더 줄일 수 있다.

왜? 기존 로직에서는 일단 트리 크기가 2000이라고 했을 때 2000번은 무조건 도는거고, 여기서 추가로 검사가 수행되는 건데.. val 값이 같을 때 즉시 검사를 하게 되면 2000번까지 가기 전에 이미 끝남

참고: 같은 트리인지 검사하는 로직은 여러 솔루션에서도 똑같이 쓰더라. 그런데 isSubtree 메서드 자체는 재귀 DFS로 풀어내는 사람이 많은 듯. 어쨌든 논리는 동일하니까.

class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {

        Queue<TreeNode> que = new ArrayDeque<>();
        que.offer(root);

        while (!que.isEmpty()) {
            TreeNode node = que.poll();
            if (node.val == subRoot.val && dfs(node, subRoot)) {
                return true;
            }

            if (node.left != null) {
                que.offer(node.left);
            }
            if (node.right != null) {
                que.offer(node.right);
            }
        }
        return false;
    }

    private boolean dfs(TreeNode node, TreeNode subRoot) {
        if (node == null && subRoot == null) {
            return true;
        }
        if (node == null || subRoot == null) {
            return false;
        }
        if (node.val != subRoot.val) {
            return false;
        }

        return dfs(node.left, subRoot.left) && dfs(node.right, subRoot.right);
    }
}

이진 트리에 대한 직렬화, 역직렬화를 구현하는 문제다. 이진트리는 배열로도 레벨 별 요소를 표현할 수 있다는 점을 활용하면 될 것 같다.

예를 들어 [1,2,3,null,null,4,5]에서 ~0번: level1, 요소 1개 ~2번: level2, 요소 2개 ~6번: level3, 요소 4개

이런 규칙으로 요소가 2의 거듭제곱으로 늘어나는 것을 볼 수 있다. 역직렬화 시 이 규칙을 통해 레벨 별 요소를 넣어줄 수 있을 거로 보인다.

풀다 보니 빵꾸난 부분이 꼭 null로 채워지진 않는듯;; 직렬화, 역직렬화 모두 Queue 이용해서 순회하도록 했다.

특히, 역직렬화는 배열 기준으로 index++하면서 요소를 찾아나가는 데에 집중했고, 직렬화의 경우 좌측부터 순서대로 넣는 것에 집중했으며 리프인 경우 하위 레벨 노드들 모두 "null"로 채워넣지 않게 방어처리 하는데 집중했다.

결과적으로 아래 코드로 정답이 나오기는 했는데, 개선해야 할 점이 많은듯

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) {
            return "[]";
        }
        StringBuilder sb = new StringBuilder("[");
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);

        while (!que.isEmpty()) {
            int size = que.size();

            boolean hasChild = false;
            List<TreeNode> nextNodes = new ArrayList<>();
            for (int i=0; i<size; i++) {
                TreeNode node = que.poll();
                if (node == null) {
                    sb.append("null,");
                } else {
                    sb.append(node.val + ",");

                    nextNodes.add(node.left);
                    nextNodes.add(node.right);

                    hasChild = hasChild || node.left != null || node.right != null;
                }
            }
            if (hasChild) {
                que.addAll(nextNodes);
            }
        }
        sb.deleteCharAt(sb.length() - 1);
        sb.append("]");

        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {

        String body = data.substring(1, data.length() - 1);
        if (body.isEmpty()) {
            return null;
        }

        String[] elements = body.split(",");
        int rootValue = Integer.parseInt(elements[0]);

        Queue<TreeNode> que = new LinkedList<>();
        TreeNode root = new TreeNode(rootValue);
        que.offer(root);

        int index = 1;
        while (!que.isEmpty() && index < elements.length) {
            int size = que.size();
            for (int i=0; i<size; i++) {
                TreeNode node = que.poll();

                String leftValue = elements[index++];
                String rightValue = elements[index++];

                if (!leftValue.equals("null")) {
                    node.left = new TreeNode(Integer.parseInt(leftValue));
                    que.offer(node.left);
                }
                if (!rightValue.equals("null")) {
                    node.right = new TreeNode(Integer.parseInt(rightValue));
                    que.offer(node.right);
                }                
            }
        }

        return root;
    }
}

GPT한테 피드백을 좀 받아보자. 아래는 GPT가 리팩터링 해준 코든데, 핵심을 요약하면 아래와 같다.

• 레벨 단위로 추가 List를 만들고 자식이 있을 때만 다음 큐에 추가하지 말고, 단순 순회하면서 다 때려 넣은다음에 마지막으로 "null"이 아닌 포인트까지 잘라서 직렬화 문자열을 구성하면 더 좋다.
• , 넣는 타이밍 수정 - i > 0일 때만 앞에 붙여주면 더 직관적이고 추후에 잘라낼 필요도 없음
• 역직렬화 로직에서, 입력값의 비정상 케이스까지 고려하려면 인덱스 경계 엄격히 체크하는 것도 좋은 방법 (이건 문제 특성 상 안해도 되는거긴 함)

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) return "[]";

        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);

        // 토큰을 리스트에 모았다가 뒤쪽의 "null" 연속 구간 제거
        List<String> tokens = new ArrayList<>();

        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            if (node == null) {
                tokens.add("null");
            } else {
                tokens.add(String.valueOf(node.val));
                q.offer(node.left);
                q.offer(node.right);
            }
        }

        // 뒤에서부터 연속된 "null"을 제거
        int last = tokens.size() - 1;
        while (last >= 0 && "null".equals(tokens.get(last))) last--;

        StringBuilder sb = new StringBuilder();
        sb.append('[');
        for (int i = 0; i <= last; i++) {
            if (i > 0) sb.append(',');
            sb.append(tokens.get(i));
        }
        sb.append(']');
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null || data.length() < 2) return null;
        String body = data.substring(1, data.length() - 1);
        if (body.isEmpty()) return null;

        String[] arr = body.split(",");
        if (arr.length == 0 || "null".equals(arr[0])) return null;

        TreeNode root = new TreeNode(Integer.parseInt(arr[0]));
        Queue<TreeNode> q = new ArrayDeque<>();
        q.offer(root);

        int i = 1;
        while (!q.isEmpty() && i < arr.length) {
            TreeNode parent = q.poll();

            // left
            if (i < arr.length && !"null".equals(arr[i])) {
                TreeNode left = new TreeNode(Integer.parseInt(arr[i]));
                parent.left = left;
                q.offer(left);
            }
            i++;

            // right
            if (i < arr.length && !"null".equals(arr[i])) {
                TreeNode right = new TreeNode(Integer.parseInt(arr[i]));
                parent.right = right;
                q.offer(right);
            }
            i++;
        }
        return root;
    }
}