TIL (2024.06.14)

문제 1️⃣ (🔗 리트 코드 _ 배열 섞기)

💡 IDEA : 두 배열을 정렬한 뒤 x 값들은 2*n 인덱스에 y 값들은 2*n+1 인덱스에 넣어 새로운 배열을 생성한다.

class Solution {
    public int[] shuffle(int[] nums, int n) {
        
        int[] answer = new int[nums.length];
        
        for (int i=0; i<n; i++) {
            answer[2*i] = nums[i];
            answer[2*i+1] = nums[i+n];
        }

        return answer;
    }
}

/*
x -> 0, 2, 4, 6 -> 2n
y -> 1, 3, 5, 7 -> 2n + 1;
*/

문제 2️⃣ (🔗 리트 코드 _ 직사각형 쿼리들)

💡 IDEA : 크게 아이디어라 할 것 없이 주어진 조건대로 작성하였다.

class SubrectangleQueries {
    int[][] rectangle;

    public SubrectangleQueries(int[][] rectangle) {
        this.rectangle = rectangle;   
    }
    
    public void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {
        for (int i=row1; i<=row2; i++) {
            for (int j=col1; j<=col2; j++) {
                rectangle[i][j] = newValue;
            }
        }
    }
    
    public int getValue(int row, int col) {
        return rectangle[row][col];
    }
}

문제 3️⃣ (🔗 프로그래머스 _ H-Index)

💡 IDEA : H 값이 될 수 있는 최소, 최댓값을 결정 한 후 이분 탐색을 통해 조건을 만족하는 최댓값을 구한다.

① H 후보값 범위 설정

➡️ H 후보값의 최솟값은 주어진 citations 배열의 최솟값 또는 배열의 길이 이다. 따라서 두 값중 Min 값을 최솟값으로 결정한다. H 후보값의 최댓값은 citations 배열의 최댓값으로 설정하였다.

② 이분 탐색 수행

➡️ 이분 탐색 수행을 통해 조건을 만족하는 값들 중 최댓값을 구한다. 이를 구하기 위해 이분탐색의 Bound 개념을 적용시켰다.

③ isPossible 전역함수 생성

➡️ 이분 탐색 과정에서 조건을 만족하는지 확인하기 위한 isPossible 함수를 생성하였다. 이 함수는 원하는 h 값이 조건을 만족하는지를 citations 배열을 맨 뒤값 (= 최댓값) 부터 확인하여 조건 만족 여부에 따라 true 또는 false 를 반환한다.

import java.util.Arrays;

class Solution {
    public int solution(int[] citations) {
        // (1) 배열 정렬
        Arrays.sort(citations);
        
        // (2) 이분 탐색 수행
        int left = Math.min(citations[0], citations.length);
        int right = citations[citations.length-1];
        int answer = 0;
        
        while (left <= right) {
            int mid = (left + right) / 2;
            
            if (isPossible(mid, citations)) {
                answer = Math.max(answer, mid);
                left = mid+1;
            }
            else {
                right = mid-1;
            }
            
        }
        
        return answer;
        
    }
    /*
        해당 h 값이 조건을 만족하는지 확인하는 함수
        int h : h 값
        int[] citations : 주어진 citations 배열
    */
    public static boolean isPossible(int h, int[] citations) {
        if (h > citations.length) return false;
        
        int min = Math.max(0, citations.length-h);
        for (int i=citations.length-1; i>=min; i--) {
            if (citations[i] < h) return false;
        }
        
        return true;
    }
}