꿀잠

https://leetcode.com/problems/serialize-and-deserialize-binary-tree/

주어진 트리 노드의 정보를 String의 형태로 변환하는 메서드, 그리고 그 String 으로 다시 노드를 만드는 메서드를 완성 시키는 문제이다. 다른 노드 간에도 같은 값이 같은 경우도 있었기에 값 뿐만 아니라 id가 필요하다고 생각하였고, id와 value 값, 그리고 노드 정보와 연결 정보를 분리하여 구현하였다. 각 값들을 분리하기 위하여 별도의 구간 분리 문자를 사용하였다. 최종 코드는 다음과 같다.

import java.util.*;  
  
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {  
  
    static String NULL_VALUE_STR = "null";  
    static String SEPARATOR = "/";  
    static String SEPARATOR_VALUE = ",";  
    static String SEPARATOR_PART = "~";  
  
    // Encodes a tree to a single string.  
    public String serialize(TreeNode root) {  
        if(root == null) return NULL_VALUE_STR;  
  
        Queue<Object[]> q = new ArrayDeque<>();  
        int id = 0;  
        q.add(new Object[]{root, id++});  
  
        StringBuilder sbValue = new StringBuilder();  
        StringBuilder sbFormation = new StringBuilder();  
  
        while(!q.isEmpty()){  
            Object[] rootInfo = q.poll();;  
            TreeNode node = (TreeNode)rootInfo[0];  
            int nodeId = (int)rootInfo[1];  
  
            sbValue.append(nodeId);  
            sbValue.append(SEPARATOR_VALUE);  
            sbValue.append(node.val);  
            sbValue.append(SEPARATOR);  
  
            sbFormation.append(nodeId);  
            sbFormation.append(SEPARATOR_VALUE);  
            int leftId = id++;  
            sbFormation.append(leftId);  
            sbFormation.append(SEPARATOR_VALUE);  
            int rightId = id++;  
            sbFormation.append(rightId);  
            sbFormation.append(SEPARATOR);  
  
            if(node.left != null){  
                q.add(new Object[]{node.left, leftId});  
            }  
            if(node.right != null){  
                q.add(new Object[]{node.right, rightId});  
            }  
        }  
        sbFormation.deleteCharAt(sbFormation.length() - 1);  
        sbValue.deleteCharAt(sbValue.length() - 1);  
        String result = sbValue.toString() + SEPARATOR_PART + sbFormation.toString();  
        return result;  
    }  
  
    // Decodes your encoded data to tree.  
    public TreeNode deserialize(String data) {  
        if(data.equals(NULL_VALUE_STR)){  
            return null;  
        }  
  
        String[] info = data.split(SEPARATOR_PART);  
        String nodeValues = info[0];  
        String nodeFormations = info[1];  
        String[] nodeIdValueArr = nodeValues.split(SEPARATOR);  
        String[] rootInfo = nodeIdValueArr[0].split(SEPARATOR_VALUE);  
        String rootKey = rootInfo[0];  
  
        Map<String, TreeNode> nodes = new HashMap<>();  
  
        for(String nodeIdValue: nodeIdValueArr){  
            String[] idValue = nodeIdValue.split(SEPARATOR_VALUE);  
            String id = idValue[0];  
            String value = idValue[1];  
            nodes.put(id, new TreeNode(Integer.parseInt(value)));  
        }  
  
        String[] nodeFormationArr = nodeFormations.split(SEPARATOR);  
        for(String nodeForamtion: nodeFormationArr){  
            String[] formation = nodeForamtion.split(SEPARATOR_VALUE);  
            String main = formation[0];  
            String left = formation[1];  
            String right = formation[2];  
            TreeNode mainNode = nodes.get(main);  
  
            if(nodes.containsKey(left)){  
                mainNode.left = nodes.get(left);  
            }  
  
            if(nodes.containsKey(right)){  
                mainNode.right = nodes.get(right);  
            }  
        }  
  
        return nodes.get(rootKey);  
    }  
}  
  
// Your Codec object will be instantiated and called as such:  
// Codec ser = new Codec();  
// Codec deser = new Codec();  
// TreeNode ans = deser.deserialize(ser.serialize(root));

문자열에서 객체를 만드는 메서드에서 맵을 이용하면 쉽게 구현할 수 있다고 생각했지만 꽤나 코드가 길어져 버렸다. 통과 후 다른 사람의 코드를 보았다. deserialize 할 때에도 Queue 를 사용한다면 값 분리도 단순하게 공백으로만 할 수 있었다. deserialize를 너무 어렵게 생각 했었던 것 같다. 아래는 통과 후 참고한 다른 해답 코드이다.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

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

        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while(!q.isEmpty()){
            TreeNode curr = q.poll();
            if(curr==null){
                sb.append("null ");
                continue;
            }
            sb.append(curr.val).append(" ");
            //no null check for left and right so that we can get null in our string.
            q.offer(curr.left);
            q.offer(curr.right);
        }
        return sb.toString();
        
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data.equals("null")) return null;

        String[] nodes = data.split(" "); //split using space to get the individual nodes

        //root using 0th string
        TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
        Queue<TreeNode> parentQ = new LinkedList<>();
        //add root as 1st parent
        parentQ.offer(root);

        for(int i=1;i<nodes.length;i++){
            TreeNode parent = parentQ.poll();
            //we handle left and right child of i-1th node
            if(!nodes[i].equals("null")){
                TreeNode leftChild = new TreeNode(Integer.parseInt(nodes[i]));
                parent.left = leftChild; //assign to parent
                parentQ.offer(leftChild); //add child to parentQ for next iteration
            }
            if(!nodes[++i].equals("null")){
                TreeNode rightChild = new TreeNode(Integer.parseInt(nodes[i]));
                parent.right = rightChild;
                parentQ.offer(rightChild);
              //  i=i+1;
            }
        }
        return root;
        
    }
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));

https://leetcode.com/problems/merge-k-sorted-lists/description/

주어진 ListNode 리스트 배열의 모든 값들을 오름차순으로 변경해야한다.
값을 기준으로 오름차순으로 하면 되기 때문에 PriorityQueue 사용시 쉽게 정렬할 수 있다.
정렬한 이후에는 poll 하며 순서대로 head에 next를 연결하면 된다.

import java.util.*;  
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {  
    public ListNode mergeKLists(ListNode[] lists) {  
        PriorityQueue<ListNode> pq = new PriorityQueue<>((node1, node2) -> node2.val - node1.val);  
        for(ListNode node: lists){  
            while(node != null){  
                pq.add(node);  
                node = node.next;  
            }  
        }  
  
        ListNode head = null;  
        ListNode next = null;  
        while(!pq.isEmpty()){  
            head = pq.poll();  
            head.next = next;  
            next = head;  
        }  
  
        return head;  
    }  
}

https://leetcode.com/problems/sliding-window-maximum/description/

주어진 길이의 구간 별 max 값을 배열로 반환 해야 하는 문제이다. 최대 값이 나온 index가 허용하는 범위 내에 새로운 최대 값이 나온다면 해당 값을 기준으로 또 다시 허용하는 구간을 정하면 된다. max 값이 나온 인덱스를 관리 추적하면서 문제를 해결해 주었다. 아래와 같은 코드로 통과하였다.

import java.util.*;  
  
public class Solution {  
    public int[] maxSlidingWindow(int[] nums, int k) {  
        int[] answer = new int[nums.length - k + 1];  
  
        int max = 0;  
        int maxIdx = 0;  
        for(int i = 0; i < k; i++){  
            if(nums[i] > max){  
                max = nums[i];  
                maxIdx = i;  
            }  
        }  
  
        int ansIdx = 0;  
        answer[ansIdx++] = max;  
  
        for(int r = k; r < nums.length; r++){  
            int num = nums[r];  
            if(nums[r] >= max){  
                max = nums[r];  
                maxIdx = r;  
            }else if(r - k >= maxIdx){  
                maxIdx = r - k + 1;  
                max = nums[maxIdx];  
                for(int i = maxIdx; i <= r; i++){  
                    if(nums[i] >= max){  
                        max = nums[i];  
                        maxIdx = i;  
                    }  
                }  
            }  
  
            answer[ansIdx++] = max;  
        }  
  
        return answer;  
    }  
}

Leetcode의 경우 문제를 통과한 이후 다른 정답들과 비교해서 속도 백분율을 보여준다. 아쉽게도 속도가 나오지 않아 다른 방식들을 확인해보았다. 다른 정답의 경우 Deque 자료구조를 이용해 유효한 max 값을 차례대로 저장해주었다. 아마도 내가 풀이한 방식의 경우 max 값이 버려질 경우 다시 추적해야 하는 방법인데 반해, 해당 방식은 갱신 될 max 값을 미리 저장해서 순회의 효율이 차이 났을 것으로 보인다.

https://leetcode.com/problems/median-of-two-sorted-arrays/description/

두 개의 숫자 배열이 주어질 때 전체 숫자의 중간 값을 찾는 문제이다. 이전에 풀었던 문제와 같은 형식의 문제였다. 당시에 풀었던 문제는 클래스를 만드는 문제였고, 이 문제는 중앙 값을 실제로 얻어내는 문제이다. 최종적으로 이번에 통과한 코드이다.

import java.util.*;  
  
public class Solution {  
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {  
  
        Median med = new Median();  
  
        for(int num: nums1){  
            med.addNum(num);  
        }  
  
        for(int num: nums2){  
            med.addNum(num);  
        }  
  
        return med.calcMedian();  
    }  
  
    private static class Median{  
  
        PriorityQueue<Integer> left = new PriorityQueue<>((a,b) -> Integer.compare(b,a));  
        PriorityQueue<Integer> right = new PriorityQueue<>();  
  
        private void addNum(int n){  
            if(left.isEmpty()){  
                left.add(n);  
            }else if(left.peek() > n){  
                left.add(n);  
            }else{  
                right.add(n);  
            }  
  
            while(right.size() > left.size()){  
                left.add(right.poll());  
            }  
  
            while(left.size() > right.size() + 1 ){  
                right.add(left.poll());  
            }  
        }  
  
        private double calcMedian(){  
            if((left.size() + right.size()) % 2 == 1){  
                return left.peek();  
            }else{  
                return (double)(left.peek() + right.peek()) / 2;  
            }  
        }  
    }  
}

아래 링크는 예전에 풀어봤던 이와 비슷한 문제와 풀이 내용이다.
https://leetcode.com/problems/find-median-from-data-stream/description/

당시에 풀었던 내용은 아래와 같다.
https://ygs3004.tistory.com/109

https://leetcode.com/problems/largest-rectangle-in-histogram/

배열로 높이가 주어지고 각 인덱스의 넓이가 1일 때 만들어지는 사각형 중 가장 큰 크기를 갖고 있는 사각형의 크기를 찾는 문제이다. 사각형을 이루는 모양은 기본적으로 양 쪽의 높이가 현재 이루고 있는 사각형보다 작을 때 해당 시점의 높이에서 최대의 넓이를 가진 사각형이 된다.

이와 같은 성질을 위해서 스택을 이용했다. 값이 순서대로 늘어나는 경우를 저장하고, 값이 감소하는 위치를 확인할 경우 해당 인덱스를 기준으로 이전 인덱스들에서 가능한 사각형의 넓이를 구할 수 있다. 스택에서 값을 하나 씩 빼며 가능한 넓이를 계산하여 최대 값을 확인하고, 해당 높이의 값들을 구했기 때문에 해당 위치의 높이를 낮은 상태라고 가정이 가능하다.

4 - 2 - 1 - 3 와 같은 높이 값이 있다면 아래와 같은 형태로 계산을 해간다.
4
4 - 2
2 - 2
2 - 2 - 1
1 - 1 - 1 - 3
1 - 1 - 1 - 1

1. 4를 스택에 저장한다.
2. 2를 저장해야 하지만 이전 값이 더 크기 때문에 2 보다 큰 스택 안의 값들을 꺼내며 넓이를 구한다.
3. 빼낸 값은 현재의 값으로 다시 저장한다.
4. 1을 저장한다.
5. 크기가 줄어 들었으므로 이전 높이가 2인 경우의 사각형 넓이를 계산한다.
6. 2 높이는 의미가 없어지고 현재 값인 1인 값으로 계산한다.
7. 3 을 저장한다.
8. 배열 전체 순회가 끝난 이후 스택에서 값을 빼며 계산해간다. 3을 계산한 이후 그 이전값으로 변경한 이후 1 높이의 넓이를 구한다.

위와 같은 규칙으로 스택을 이용하여 통과한 최종 코드는 아래와 같다.

import java.util.*;  
  
public class Solution {  
    public int largestRectangleArea(int[] heights) {  
        int answer = 0;  
        Deque<Integer> stack = new ArrayDeque<>();  
        stack.addLast(heights[0]);  
  
        int width;  
        for(int i = 1; i < heights.length; i++){  
            int h1 = heights[i];  
            width = 1;  
            while(!stack.isEmpty() && stack.peekLast() > h1){  
                int h2 = stack.pollLast();  
                answer = Math.max(h2 * width, answer);  
                width++;  
            }  
  
            while(width-- > 0){  
                stack.addLast(h1);  
            }  
        }  
  
        width = 1;  
        while(!stack.isEmpty()){  
            int h2 = stack.pollLast();  
            answer = Math.max(h2 * width, answer);  
            width++;  
        }  
  
        return answer;  
    }  
}

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/

더해서 목표 값이 되는 두 점을 찾는 문제이다. 이 때 배열은 정렬되어있다. 문제는 그리 어렵지 않고 단순하게 for문 안에서 합계를 넘어가는 수준까지 순환을 하며 값이 완성되는지 확인해도 된다.
하지만 정렬되어있는 배열이기 때문에 이진 탐색을 사용 하는 것이 효율적이다.

목표 값을 찾기 위해 좌측 포인트를 고정하고, 적절한 우측 포인트 값이 있는지 이진 탐색으로 탐색하여 문제를 통과했다.

public class Solution {  
    public int[] twoSum(int[] numbers, int target) {  
  
        for(int i = 0; i < numbers.length - 1; i++){  
            int find = target - numbers[i];  
            int l = i + 1;  
            int r = numbers.length - 1;  
  
            while(l <= r){  
                int mid = l + (r - l) / 2;  
                int now = numbers[mid];  
                if(now == find){  
                    return new int[]{i + 1, mid + 1};  
                }  
  
                if(now > find){  
                    r = mid - 1;  
                }else{  
                    l = mid + 1;  
                }  
            }  
        }  
  
        return null;  
    }  
}

https://leetcode.com/problems/top-k-frequent-elements/description/

배열에 k 번째까지 높은 빈도수를 갖는 숫자를 찾아서 배열로 반환하는 문제이다.
Map, PriorityQueue, 자료구조를 이용하여 해결하였다. 빈도수를 체크하기 위해 Map의 key,value 를 이용하였고, 높은 빈도수를 갖는 숫자로 정렬하기 위해서 PriorityQueue와 Comparable을 구현한 클래스를 만들어 주었다. 통과 코드는 아래와 같다.

import java.util.*;  
  
public class Solution {  
    public int[] topKFrequent(int[] nums, int k) {  
        Map<Integer, Element> map = new HashMap<>();  
  
        for(int num: nums){  
            map.compute(num, (key, element) -> {  
                if(element == null){  
                    element = new Element(num);  
                }else{  
                    element.freq++;  
                }  
                return element;  
            });  
        }  
  
        PriorityQueue<Element> pq = new PriorityQueue<>();  
        for(Element e : map.values()){  
            pq.add(e);  
        }  
  
        int[] answer = new int[k];  
        for(int i = 0; i < k; i++){  
            answer[i] = pq.poll().value;  
        }  
  
        return answer;  
    }  
  
    private static class Element implements Comparable<Element>{  
        int value;  
        int freq;  
  
        Element(int value){  
            this.value = value;  
            this.freq = 1;  
        }  
  
        @Override  
        public int compareTo(Element o){  
            return o.freq - this.freq;  
        }  
    }  
}

https://leetcode.com/problems/happy-number/description/

주어진 조건을 만족하는지 체크하는 문제이다. 단순 수식 구현 문제로 문제에서 제시하는 조건들을 따라 해결해 나가면 된다. 숫자를 10의 자리 단위로 분해하여 제곱 해서 더해야 하므로 %, / 연산자를 써서 해결해 나가면 된다. 최종 조건인 1이 되는 경우 외에도 무한히 반복되는 경우로 4가 있었다. 이를 체크하기 위해 set을 이용하여 사이클 체크를 해주었다.

import java.util.*;  
  
public class Solution {  
    public boolean isHappy(int n) {  
        Set<Integer> set = new HashSet<>();  
  
        while(n > 1){  
            int sum = 0;  
            while(n > 0){  
                int mod = n % 10;  
                sum += mod * mod;  
                n = n / 10;  
            }  
  
            n = sum;  
            if(set.contains(n)) break;  
            set.add(n);  
        }  
  
        return n == 1;  
    }  
}