꿀잠

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/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/find-minimum-in-rotated-sorted-array/description/

값이 정렬된 배열이 존재할 때 이 배열을 왼쪽으로 회전 시킨 배열이 매개 변수로 주어진다.
원본 배열의 최소 값이자 0번 인덱스의 값은 무엇인지 찾는 문제이다. 이진 탐색을 이용하여 해결할 수 있고 mid 값을 기준으로 왼쪽, 또는 오른쪽은 정확히 정렬되어있다는 점을 이용해 반복 탐색할 수 있다.

왼쪽으로 회전 되기 때문에 만약 우측 끝 값이 중앙 값보다 크다면 우측 부분은 제대로 정렬되어 있다고 할 수 있다. 이 때 우측이 제대로 정렬 되어 있다면 현재의 mid가 원점이 될 수 있다는 점을 생각해 탐색을 할 때 현재 mid 값을 이어 가야 한다. 아래는 최종 코드이다.

public class Solution {  
    public int findMin(int[] nums) {  
        int l = 0;  
        int r = nums.length - 1;  
        int mid = (l + r) / 2;  
  
        while(l <= r){  
            mid = l + (r - l) / 2;  
            int n = nums[mid];  
  
            // 오른쪽이 정렬  
            if(n < nums[r]){  
                r = mid;  
            // 왼쪽이 정렬된 경우  
            }else{  
                l = mid + 1;  
            }  
        }  
  
        return nums[mid];  
    }  
  
}

https://leetcode.com/problems/search-in-rotated-sorted-array/description/

배열에서 타겟의 값을 찾는 문제이다. 특이점으로는 배열이 정렬되어있으나 해당 정렬은 왼쪽으로 회전 되어있을 수 있다는 점이다.

사실 문제 요구 사항으로 O(log n) 시간 복잡도를 요구하나 단순 for문(시간 복자도 O(n))으로 찾아도 문제가 통과된다. 하지만 알고리즘 연습을 위해 푸는 문제이니 정석적인 방법으로 풀었다.
O(log n)의 시간 복잡도를 요구한다는 것은 이진 탐색 알고리즘을 사용하라는 것으로 이해하면 된다.

단 조건이 회전된 배열일 수 있으므로 조건을 더 세분화 하여야 한다.
우선 이진탐색을 위해 left, right, mid 를 선정한 이후 조건을 세분화하여 left, right 의 값을 변화시키며 이진 탐색을 하여 해결하였다. 조건 선정에 자꾸 실패하여 꽤나 고생했다. 아래는 최종적으로 통과한 코드이다.

mid를 중심으로 왼쪽 또는 오른쪽은 신뢰할 수 있게 정렬 되어있다는 점을 이용하여 조건을 나누었다.

public class Solution {  
    public int search(int[] nums, int target) {  
        int left = 0;  
        int right = nums.length - 1;  
        while(left <= right){  
            int mid = (left + right) / 2;  
            int s = nums[left];  
            int e = nums[right];  
            int cur = nums[mid];  
  
            if(target == cur){  
                return mid;  
            }  
  
            if(cur >= s){  
                // 왼쪽이 정렬되어있을 경우  
                if(target > cur){  
                    left = mid + 1;  
                }else if(target >= s){  
                    right = mid - 1;  
                }else{  
                    left = mid + 1;  
                }  
            }else{  
                // 오른쪽이 정렬되어있을 경우  
                if(target < cur){  
                    right = mid - 1;  
                }else if(target <= e){  
                    left = mid + 1;  
                }else{  
                    right = mid - 1;  
                }  
            }  
        }  
  
        return -1;  
    }  
}

https://leetcode.com/problems/binary-search/description/

이진탐색 알고리즘을 알고있는지 체크하는 문제로 O(log n) 시간복잡도를 요구한다.
특이점으로는 존재하지 않는 값을 타겟으로 하는 문제가 존재하고 그럴경우 -1 값을 리턴해야 한다는 것이다.

이진 탐색을 위해 low, high 값을 설정하고 mid를 인덱스로 하여 값을 비교하고, 값에 따라 low, high 미드값을 변경하여 mid 인덱스로 타겟을 찾아가는 방식이다

class Solution {  
    public int search(int[] nums, int target) {  
        int len = nums.length;  
        int low = 0;  
        int high = len - 1;  
        int mid = (low + high) / 2;  
  
        // while 의 조건문을 통해 타겟에 도달했는지 확인  
        while(nums[mid] != target){  
            int cur = nums[mid];  
            if(cur > target){  
                // index 범위를 초과하거나, 답이 없거나를 체크  
                if(mid - 1 < 0 || nums[mid - 1] < target){  
                    mid = -1;  
                    break;  
                }  
                // 중간점 체크를 위해 값 비교를 통해, low - high 값 전환  
                high = mid - 1;  
  
            }else{  
                // index 범위를 초과하거나, 답이 없거나를 체크  
                if(mid + 1 >= nums.length || nums[mid + 1] > target){  
                    mid = -1;  
                    break;  
                }  
  
                // 중간점 체크를 위해 값 비교를 통해, low - high 값 전환  
                low = mid + 1;  
            }  
            // 변경된 low, high 값을 이용해 새로운 중간점 변경  
            mid = (high + low) / 2;  
        }  
  
        return mid;  
    }  
}

답이 없는 부분을 체크하기 위해, 바로 근처 값을 확인 하는 방식을 넣었다.

이 때 인덱스가 배열의 범위를 초과하는지 체크하지 않으면 배열의 범위를 초과하는 인덱스 값을 검사하여

오류를 발생 시킬 수 있다.

이진 탐색 문제를 풀 때는 항상 범위를 잘못 처리하거나,

인덱스 조정 시 실수하여 while문을 탈출하지 못하는 실수를 할 때가 많다.

다행히 해당 문제는 조건이 까다롭지 않고 기초적인 이진탐색을 요구하기에 이진탐색을 입문하기 좋은 문제였다.