LeetCode - Weekly Contest 296 풀이 및 후기

 

2293. Min Max Game

난이도: Easy

---

You are given a 0-indexed integer array nums whose length is a power of 2.

Apply the following algorithm on nums:

1. Let n be the length of nums. If n == 1, end the process. Otherwise, create a new 0-indexed integer array newNums of length n / 2.
2. For every even index i where 0 <= i < n / 2, assign the value of newNums[i] as min(nums[2 * i], nums[2 * i + 1]).
3. For every odd index i where 0 <= i < n / 2, assign the value of newNums[i] as max(nums[2 * i], nums[2 * i + 1]).
4. Replace the array nums with newNums.
5. Repeat the entire process starting from step 1.

Return the last number that remains in nums after applying the algorithm.

 

Example 1:

Input: nums = [1,3,5,2,4,8,2,2]
Output: 1
Explanation: The following arrays are the results of applying the algorithm repeatedly.
First: nums = [1,5,4,2]
Second: nums = [1,4]
Third: nums = [1]
1 is the last remaining number, so we return 1.

Example 2:

Input: nums = [3]
Output: 3
Explanation: 3 is already the last remaining number, so we return 3.

 

Constraints:

• 1 <= nums.length <= 1024
• 1 <= nums[i] <= 109
• nums.length is a power of 2.

문제 설명 

 배열 nums가 주어질 때 nums의 길이가 1이 될 때까지 다음 알고리즘을 반복하는 문제입니다.

 

배열을 두개 씩 묶어서 차례대로 홀수 차례일 때 최솟값을 짝수 차례일 때 최댓값을 리턴한다. 

 

접근법

 

flag 변수를 선언하여 2개씩 묶은 배열이 홀수번째 인지 또는 짝수 번째인지 체크한다

그리고 재귀함수를 통해 nums의 길이가 1이 될 때까지 반복해준다. 

 

코드

/**
 * @param {number[]} nums
 * @return {number}
 */
var minMaxGame = function(nums) {
    if(nums.length === 1) return nums[0]
    let arr = [] 
    let flag = true
    for(let i=2; i<=nums.length; i+=2){
        const num = flag ? Math.min(...nums.slice(i-2,i)) : Math.max(...nums.slice(i-2,i))
        flag = !flag
        arr.push(num)
    }
    return minMaxGame(arr)
};

 

2294. Partition Array Such That Maximum Difference Is K

난이도: Medium

---

You are given an integer array nums and an integer k. You may partition nums into one or more subsequences such that each element in nums appears in exactly one of the subsequences.

Return the minimum number of subsequences needed such that the difference between the maximum and minimum values in each subsequence is at most k.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

 

Example 1:

Input: nums = [3,6,1,2,5], k = 2
Output: 2
Explanation:
We can partition nums into the two subsequences [3,1,2] and [6,5].
The difference between the maximum and minimum value in the first subsequence is 3 - 1 = 2.
The difference between the maximum and minimum value in the second subsequence is 6 - 5 = 1.
Since two subsequences were created, we return 2. It can be shown that 2 is the minimum number of subsequences needed.

Example 2:

Input: nums = [1,2,3], k = 1
Output: 2
Explanation:
We can partition nums into the two subsequences [1,2] and [3].
The difference between the maximum and minimum value in the first subsequence is 2 - 1 = 1.
The difference between the maximum and minimum value in the second subsequence is 3 - 3 = 0.
Since two subsequences were created, we return 2. Note that another optimal solution is to partition nums into the two subsequences [1] and [2,3].

Example 3:

Input: nums = [2,2,4,5], k = 0
Output: 3
Explanation:
We can partition nums into the three subsequences [2,2], [4], and [5].
The difference between the maximum and minimum value in the first subsequences is 2 - 2 = 0.
The difference between the maximum and minimum value in the second subsequences is 4 - 4 = 0.
The difference between the maximum and minimum value in the third subsequences is 5 - 5 = 0.
Since three subsequences were created, we return 3. It can be shown that 3 is the minimum number of subsequences needed.

 

Constraints:

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 105
• 0 <= k <= 105

문제 설명 

배열 nums 와 최댓값 최솟값 차이를 나타내는 k 가 주어질 때,

조건(최댓값 - 최솟값 <= k)을 만족하는 nums를 나눌 수 있는 가장 작은 수를 구하는 문제이다.

 

접근법

nums를 내림 차순 정렬하고 for문을 통해 주어진 조건(최대값 - 최소값 <= k)을 만족하는지 확인한다.

코드

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var partitionArray = function(nums, k) {
    nums.sort((a,b)=>b-a)
    let maxNum =  nums[0]
    let count = 1 
    //가장 작은값
    for(let i=1; i<nums.length; i++){
        if(maxNum - nums[i] > k){
            count++
            maxNum  = nums[i]
        }
    }
    return count
};

 

2295. Replace Elements in an Array

난이도: Medium

---

You are given a 0-indexed array nums that consists of n distinct positive integers. Apply m operations to this array, where in the ith operation you replace the number operations[i][0] with operations[i][1].

It is guaranteed that in the ith operation:

• operations[i][0] exists in nums.
• operations[i][1] does not exist in nums.

Return the array obtained after applying all the operations.

 

Example 1:

Input: nums = [1,2,4,6], operations = [[1,3],[4,7],[6,1]]
Output: [3,2,7,1]
Explanation: We perform the following operations on nums:
- Replace the number 1 with 3. nums becomes [3,2,4,6].
- Replace the number 4 with 7. nums becomes [3,2,7,6].
- Replace the number 6 with 1. nums becomes [3,2,7,1].
We return the final array [3,2,7,1].

Example 2:

Input: nums = [1,2], operations = [[1,3],[2,1],[3,2]]
Output: [2,1]
Explanation: We perform the following operations to nums:
- Replace the number 1 with 3. nums becomes [3,2].
- Replace the number 2 with 1. nums becomes [3,1].
- Replace the number 3 with 2. nums becomes [2,1].
We return the array [2,1].

 

Constraints:

• n == nums.length
• m == operations.length
• 1 <= n, m <= 105
• All the values of nums are distinct.
• operations[i].length == 2
• 1 <= nums[i], operations[i][0], operations[i][1] <= 106
• operations[i][0] will exist in nums when applying the ith operation.
• operations[i][1] will not exist in nums when applying the ith operation.

문제 설명

nums와 operations이 입력값으로 주어진다. 

이때, operations[i][0] 이 nums에 존재하면 operations [i][1]로 값을 변경하는 문제이다.

 

접근법

단순하게 2중 for문을 통해 문제를 풀게 되면 시간 초과가 발생하기 때문에

 

nums에 operataions[i][0] 이 존재할 경우 해당 값을 쉽게 변경해주기 위해

list obj에 key, value값으로 nums의 값과 인덱스 번호를 저장 해준 뒤 for문을 순회한다.!

 

코드

/**
 * @param {number[]} nums
 * @param {number[][]} operations
 * @return {number[]}
 */
var arrayChange = function(nums, operations) {
    const list = {}
    for(let i=0; i<nums.length;i++){
        list[nums[i]] = i
    }
   for(let i=0; i<operations.length; i++){

       const idx = list[operations[i][0]] === undefined ?   -1 : list[operations[i][0]]
       // list에 operations[i][0]이 존재하면
       if(idx >= 0 ){
           nums[idx] = operations[i][1]
           delete list[operations[i][0]]
           list[operations[i][1]] = idx
       }
   }
   
    return nums
};

 

 

1,2,3번 모두 풀고 30분이 남았지만 시간이 부족해서 3 솔로 마무리했습니다.!

4번은... 디자인 문제였는데 아직은 어렵네요 ㅎㅎㅎ 

더 좋은 방법 있으면 댓글로 남겨 주세요~