꿀잠

https://leetcode.com/problems/find-median-from-data-stream/description/

주어진 클래스의 메서드를 완성시키는 문제이다. 이 때 입력된 숫자 값들의 중간 값, 짝수개 일 경우 중간 값 두 가지를 더한 후 나눈 값을 리턴시켜야 하는 메서드가 존재한다. 일반적인 List, LinkedList를 이용한 후 size 값으로 인덱스를 찾을 경우 시간 초과에 걸리게 된다.

문제를 해결하기 위해서 정렬에 효율적인 PriorityQueue를 이용하고, 중간 값을 찾기 편하게 하기 위하여 두 구간으로 나누었다. left 구간은 right 값보다 작은 값들로 peek 할 경우 중간 값, 짝수 사이즈일 때는 작은 중간 값을 확인할 수 있다. right 구간은 peek 할 경우 짝수 사이즈일 때 큰 중간 값을 확인할 수 있다. 이를 위해서 left PriorityQueue는 내림차순으로 Comperator를 설정해주어야 한다.

addNum 함수는 값이 들어오는 함수이다. 기본적으로 left의 조건을 확인하고 추가하고, 아닐 경우 right에 추가한다. 하지만 left에만 값이 쌓일 수 있는 경우의 수가 있으므로 사이즈를 비교해서 바로 left,right 균형을 맞춰 주었다.

addNum 함수와 PriorityQueue 두 구간으로 나누기를 완성했으면 중간 값을 구하는 메서드는 간단해진다. 홀 수 사이즈는 left에서 확인 가능하고 짝 수 사이즈는 left와 right에서 확인 가능하다. 단 값이 비어있는 경우 peek() 메서드에서 NullPointerException 이 발생할 수 있으므로 예외 값을 별도로 분기처리해주었다.

import java.util.*;  
  
class MedianFinder {  
  
    PriorityQueue<Integer> left;  
    PriorityQueue<Integer> right;  
  
    public MedianFinder() {  
        left = new PriorityQueue<>((a,b) -> Integer.compare(b, a));  
        right = new PriorityQueue<>();  
    }  
  
    public void addNum(int num) {  
        if(left.isEmpty()){  
            left.add(num);  
        }else if(left.peek() > num){  
            left.add(num);  
        }else{  
            right.add(num);  
        }  
  
        while(right.size() > left.size()){  
            left.add(right.poll());  
        }  
  
        while(left.size() > right.size() + 1){  
            right.add(left.poll());  
        }  
    }  
  
    public double findMedian() {  
  
        double median = 0;  
        int size = left.size() + right.size();  
          
        if(size == 0){  
            return median;  
        }else if(size % 2 == 0){  
            median = (double)(left.peek() + right.peek())/2;  
        }else{  
            median = left.peek();  
        }  
  
        return median;  
    }  
}  
  
/**  
 * Your MedianFinder object will be instantiated and called as such: 
 * MedianFinder obj = new MedianFinder(); 
 * obj.addNum(num); 
 * double param_2 = obj.findMedian(); 
 */

https://leetcode.com/problems/binary-tree-maximum-path-sum/

주어진 이진 트리 노드를 하나의 길로 연결 했을 때 가장 큰 누적 합의 값을 찾는 문제이다.

특정 노드에서 길을 잇기 위해선 좌우 노드와 이어지거나, 좌 또는 우 노드 중 하나와 상위 노드와의 연결이 되는 경우이다. 이러한 규칙으로 재귀적으로 순환하며 특정 노드에서 좌,우 노드와의 합계의 최대 값을 결과 값으로 구할 수 있다.

아래는 통과된 코드이다. 주의할 점은 return 해서 상위 노드로 보내는 값과 해당 노드에서 가능한 최대 값의 계산 방식이 다르다는 점이다.

class Solution {  
  
    int answer;  
  
    public int maxPathSum(TreeNode root) {  
        this.answer = Integer.MIN_VALUE;  
        recursiveNode(root);  
        return answer;  
    }  
  
    public int recursiveNode(TreeNode root){  
  
        if(root == null) return 0;  
  
        int val1 = root.val;  
        int val2 = Math.max(recursiveNode(root.left), 0);  
        int val3 = Math.max(recursiveNode(root.right), 0);  
  
        int maxValue = val1 + val2 + val3;  
        answer = Math.max(maxValue, answer);  
  
        return val1 + Math.max(val2, val3);  
    }  
}

https://leetcode.com/problems/reorder-list/description/

주어진 ListNode 의 순서를 주어진 규칙으로 재 정렬하는 문제이다. 순서대로 있던 노드를 앞,끝의 순서대로 정렬해야 한다. 이렇게 앞, 뒤에서 값을 뽑아야 할 때 쓰기 좋은 자료로 Deque가 있다. Deque는 자료 구조의 앞과 뒤에 값을 넣거나 뺄 수 있는 자료구조이다.

이를 이용하기 위해 주어진 노드를 Deque에 전부 넣은 뒤 순서대로 앞, 뒤에서 값을 빼서 연결하면 문제를 풀이할 수 있다.

/**  
 * 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; } 
   * } 
   */
   
import java.util.*;  
  
class Solution {  
    public void reorderList(ListNode head) {  
        Deque<ListNode> deque = new ArrayDeque<>();  
  
        ListNode node = head.next;  
        while(node != null){  
            deque.addLast(node);  
            node = node.next;  
        }  
  
        int i = 0;  
        while(!deque.isEmpty()){  
            ListNode next = null;  
            if(i % 2 == 0){  
                next = deque.pollLast();  
            }else{  
                next = deque.pollFirst();  
            }  
  
            head.next = next;  
            head = next;  
            i++;  
        }  
  
        head.next = null;  
    }  
  
}

https://leetcode.com/problems/longest-repeating-character-replacement/description/

특정 구간의 문자열이 하나로만 이루어져 있을 때 가장 긴 구간을 체크하는 문제이다. 단 k 개의 개수까지 다른 문자를 허용한다.

정답을 구하기 위하여 배열을 이용하여 글자 수가 늘어나는 것을 체크해주었다. 이 때 특정 길이까지 한번 체크한 이후에는 그 길이 이상일 경우만 정답이 될 수 있다는 점을 이용해 길이 조건을 유지할 수 있다. 반복된 문자 개수와 k의 합계가 현재의 길이보다 크다면 left를 증가 시켜 길이를 체크해 주었다. 아래는 전체 통과 코드이다.

public class Solution {  
    public int characterReplacement(String s, int k) {  
        int[] current = new int[26];  
        int maxRepeat = 0;  
        int answer = 0;  
        int l = 0;  
  
        for(int r = 0; r < s.length(); r++){  
            char now = s.charAt(r);  
            current[now - 'A']++;  
            maxRepeat = Math.max(maxRepeat, current[now - 'A']);  
  
            if(r - l + 1 - maxRepeat > k){  
                current[s.charAt(l) - 'A']--;  
                l++;  
            }  
  
            answer = Math.max(r - l + 1, answer);  
        }  
  
        return answer;  
    }  
}

https://leetcode.com/problems/koko-eating-bananas/description/

각 배열의 값을 바나나의 개수라고 할 때, 한 인덱스를 먹을 때 임의의 속도로 먹을 때 주어진 시간 내에 다 먹기 위해 필요한 최소 시간을 구하는 문제이다.

특이 사항으로는 인덱스를 전부 다 완료하더라도 시간 단위가 끝날 때 까지는 다음 인덱스를 먹지 못한다는 것이다. 이 부분은 나머지의 존재 여부에 따라 시간 계산을 변경하여 해결해 줄 수 있다. 그리고 이 문제의 최소 시간을 구하기 위해서는 이진 탐색을 사용하는 것이 좋다. 최소~, 최대~ 이런 형태의 문제는 이진 탐색 문제일 가능성이 크다. 정답이 될 수 있는 값이 특정 범위일 때 이 범위의 최대 값, 최소 값을 찾기 위해 좋은 알고리즘 이기 때문이다.

이와 같은 부분을 감안하고 문제를 풀면 풀 수 있지만, 하나의 테스트 케이스에서 걸렸었다. 총 시간의 합계를 구하는 부분에서 오버플로우가 발생했다. 이를 해결하기 위해 합계가 아니라 차이를 이용하는 방법을 사용했다. 하지만 이 차이를 이용하는 부분도 오버플로우가 발생할 수 있을 것 같다. 따라서 long타입을 사용하는 것이 더 좋았을 것 같다. 아래는 시간 계산을 위해서 차이(뺄셈)을 이용해서 문제에 통과한 코드이다.

public class Solution {  
    public int minEatingSpeed(int[] piles, int h) {  
        int low = 1;  
        int high = Integer.MIN_VALUE;  
        for (int i = 0; i < piles.length; i++) {  
            high = Math.max(piles[i], high);  
        }  
  
        int mid = 0;  
        int k = Integer.MAX_VALUE;  
  
        while (low <= high) {  
            mid = low + (high - low) / 2;  
            // int time = 0;  
            int time = h;  
            for (int i = 0; i < piles.length; i++) {  
                int pile = piles[i];  
                // time += pile % mid == 0 ? pile / mid : pile / mid + 1;  // [805306368,805306368,805306368] overflow  
                time -= pile % mid == 0 ? pile / mid : pile / mid + 1;  
            }  
  
            // if(time <= h){  
            if (time >= 0) {  
                high = mid - 1;  
                k = Math.min(k, mid);  
            } else {  
                low = mid + 1;  
            }  
        }  
  
        return k;  
    }  
}

https://leetcode.com/problems/generate-parentheses/description/

주어진 n의 개수에 따라 열고 닫히는 괄호를 만드는 문제이다. 괄호는 Stack 자료구조 문제 관련해서 자주 등장하는 알고리즘 문제이다. 괄호를 여는 부분이 먼저 나오고 닫히는 부분이 뒤에 나오기 때문에 스택에 저장하고 꺼낼 때 괄호를 완성해 줄 수 있기 때문이다.

하지만 해당 문제는 소괄호 하나만 등장하기 때문에 스택을 특별히 사용할 필요는 없었다. 문자열을 만들면서 열려있는 괄호가 닫히는 괄호가 생성되기 전에 충분히 있는지, 그리고 최종적으로 완성된 문자열의 경우 열고 닫히는 괄호의 숫자가 알맞게 있는지 체크해주면 되었다. 문자열을 생성하는 과정은 백트래킹 형태의 dfs를 이용해 주었고, 효율을 높이기 위해 괄호가 완성되는 형태를 가질 수 없는 경우를 필터링 해주었다. 아래는 통과한 코드이다.

public class Solution {  
  
    static String[] letter = {"(", ")"};  
  
    public List<String> generateParenthesis(int n) {  
        List<String> answer = new ArrayList<>();  
        StringBuilder sb = new StringBuilder();  
        sb.append("(");  
        dfs(n * 2, sb, answer);  
  
        return answer;  
    }  
  
    private void dfs(int n, StringBuilder sb, List<String> answer){  
        boolean isLast = n == sb.length();  
        if(!isPossible(sb.toString(), isLast)){  
            return;  
        }  
  
        if(isLast){  
            answer.add(sb.toString());  
            return;  
        }  
  
        for(int i = 0; i < 2; i++){  
            sb.append(letter[i]);  
            dfs(n, sb, answer);  
            sb.deleteCharAt(sb.length() - 1);  
        }  
    }  
  
    private boolean isPossible(String str, boolean isComplete){  
        int check = 0;  
        for(char c: str.toCharArray()){  
            if(c == '('){  
                check++;  
            }else{  
                if(check == 0){  
                    return false;  
                }  
  
                check--;  
            }  
        }  
  
        return isComplete ? check == 0 : true;  
    }  
  
}

괄호를 체크하기 위해 문자열을 char 배열로 변환해서 해주었는데, 다른 코드들을 참고하니 재귀를 돌면서 left와 right 개수를 단순 int 값으로 처리해서 확인하는 방법이 속도가 좋아서 다음에 괄호 관련된 문제 풀이 시 참고할 방법을 얻을 수 있었다.

https://leetcode.com/problems/trapping-rain-water/description/

주어진 높이 배열에 물을 담을 수 있는 양을 체크하는 문제이다. 처음 문제를 보았을 때는 쉽게 풀 수 있을거라 생각했지만 막상 풀이를 시도하니 고려해야 할 문제들이 많았다. 좌우 높이 뿐만 아니라 바닥의 높이도 가변적이다 보니 넓이를 구하기가 쉽지 않았다.

바닥의 높이가 좌표마다 다른 점을 해결하기 위해 좌우 벽과 함께 계산된 바닥도 이동 시켜주는 방식으로 생각해주었다. 좌,우 포인트를 더 높은 곳으로 이동시키며 이미 계산한 벽의 높이 만큼은 바닥을 잘라준다고 생각하여 물의 양을 계산해주는 것을 반복하여 풀었다. 아래는 최종 코드이다.

public class Solution {  
    public int trap(int[] height) {  
  
        int answer = 0;  
        int bottom = 0;  
        int l = 0;  
        int r = height.length - 1;  
  
        while(l < r){  
            int leftHeight = height[l];  
            int rightHeight = height[r];  
            int minHeight = Math.min(leftHeight, rightHeight);  
            for(int i = l; i <= r; i++){  
                int nowHeight = height[i];  
                if(nowHeight < minHeight){  
                    answer += minHeight - Math.max(nowHeight, bottom);  
                }  
            }  
  
            bottom = minHeight;  
            if(leftHeight > rightHeight){  
                while(l < r && height[r] <= rightHeight){  
                    r--;  
                }  
            }else{  
                while(l < r && height[l] <= leftHeight){  
                    l++;  
                }  
            }  
        }  
  
        return answer;  
    }  
}

직접 풀이한 내용 외에도 다른 풀이에서 눈에 보였던 점은 좌우 벽의 최대 높이를 배열로 저장해두고 사용하는 방식이었다. 점을 이동시켜 현재 높이를 구하면서도 현재 높이에서 좌우 높이의 최대 값을 확인하는 방식으로 속도 효율이 좋았다. 해당 코드는 아래와 같다.

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int lmax[] = new int[height.length];   
        int rmax[] = new int[height.length];
        int l_max = height[0];
        for(int i=0;i<n;i++){
            l_max = Math.max(l_max,height[i]);
            lmax[i] = l_max;
        }
        int r_max = height[n-1];
        for(int i=n-1;i>=0;i--){
            r_max = Math.max(r_max,height[i]);
            rmax[i] = r_max;
        }
        int count = 0;
        for(int i=0;i<n;i++){
            count+=(Math.min(lmax[i],rmax[i])-height[i]);
        }
        return count;
    }
}

https://leetcode.com/problems/group-anagrams/

동일한 문자로 구성된 문자열을 묶어주는 문제이다. 문자를 분해한 이후 정렬해주면 그 구성을 확인할 수 있다. 이 확인한 결과를 Map 구조의 키로 이용해주어 각 단어들의 리스트를 만들어 줄 수 있다. 아래의 코드와 같이 해결해 줄 수 있다.

import java.util.*;  
  
public class Solution {  
    public List<List<String>> groupAnagrams(String[] strs) {  
        Map<String, List<String>> map = new HashMap<>();  
        for(String str: strs){  
            char[] c = str.toCharArray();  
            Arrays.sort(c);  
            String reArrange = new String(c);  
            if(!map.containsKey(reArrange)){  
                map.put(reArrange, new ArrayList<>());  
            }  
  
            map.get(reArrange).add(str);  
        }  
  
        return new ArrayList<>(map.values());  
    }  
}