TIL (2024.06.12)

문제 1️⃣ (🔗 리트 코드 _ 정렬된 이차원 배열에서 음수찾기)

💡 IDEA : 정렬되어있는 배열이므로 이분탐색을 통해 탐색 속도를 높인다. 이때, 위아래에 대해서도 정렬이 되어있음으로 다음 배열 탐색시 전 배열 탐색 결과를 바탕으로 범위를 좁혀서 탐색할 수 있다.

IDEA 설명

class Solution {
    public int countNegatives(int[][] grid) {
        int answer = 0;

        int m = grid.length; // 세로 길이
        int n = grid[0].length; // 가로 길이

        int left = 0;
        int right = n-1;
        int idx = n;
        int mid = 0;

        for (int i=0; i<m; i++) {
            if (idx == 0){
                answer += (m-i)*n;
                break;
            }
            left = 0;
            right = idx-1;

            // 이분 탐색 수행
            while (left <= right) {
                mid = (left + right) / 2;

                if (grid[i][mid] < 0) {
                    right = mid - 1;
                    idx = Math.min(idx, mid);
                }
                else {
                    left = mid + 1;
                }
            }
            
            answer += (n-idx);
        }

        return answer;
    }
}

 

문제 2️⃣ (🔗 리트 코드 _ 짐  옮기기)

💡 IDEA : 제시된 날 안에 짐을 옮길 수 있는지는 완전 탐색을 통해 알 수 있다. 다만 무게 제한을 이분 탐색을 통해서 속도를 개선할 수 있다.

class Solution {
    public int shipWithinDays(int[] weights, int days) {
    
    	// (1) 탐색할 무게의 범위를 결정
        int sum = 0;
        int max = 0;

        for (int weight : weights) {
            sum += weight;
            max = Math.max(max, weight);
        }
        
        // (2) 이분 탐색 수행
        int left = max;
        int right = sum;
        int minDay = sum+1;

        while (left <= right) {
            int mid = (left + right) / 2;
            
            if (isPossible(weights, days, mid)) {
            	// LowerBound 개념을 통해 최소값을 탐색
                minDay = Math.min(mid, minDay);
                right = mid-1;
            }
            else {
                left = mid+1;
            }
        }

        return minDay;
    }
    
    /*
    	int[] weights : 주어진 무게 배열
        int days : 주어진 날짜 제한
        int limit : 탐색 중인 무게 제한
    */
    public static boolean isPossible (int[] weights, int days, int limit) {

        int sum = 0;
        int cnt = 1;
		
        // 제시된 limit 무게에 대해서 모든 짐을 옮기려면 얼마나 걸리는지 확인
        for (int i=0; i<weights.length; i++) {
            if (sum + weights[i] <= limit) {
                sum += weights[i];
                continue;
            }
            else {
                sum = weights[i];
                cnt++;
            }
        }
		
        // 제한된 날짜 안에 끝나면 true 를 반환
        return cnt <= days;
    }
}