221114 :: [leetcode] Shift 2D Grid, Add Digits, Append K Integers With Minimal Sum

Shift 2D Grid

Given a 2D grid of size m x n and an integer k. You need to shift the grid k times.

In one shift operation:

• Element at grid[i][j] moves to grid[i][j + 1].
• Element at grid[i][n - 1] moves to grid[i + 1][0].
• Element at grid[m - 1][n - 1] moves to grid[0][0].

Return the 2D grid after applying shift operation k times.

 

Example 1:

Input: grid = [[1,2,3],[4,5,6],[7,8,9]], k = 1
Output: [[9,1,2],[3,4,5],[6,7,8]]

Example 2:

Input: grid = [[3,8,1,9],[19,7,2,5],[4,6,11,10],[12,0,21,13]], k = 4
Output: [[12,0,21,13],[3,8,1,9],[19,7,2,5],[4,6,11,10]]

Example 3:

Input: grid = [[1,2,3],[4,5,6],[7,8,9]], k = 9
Output: [[1,2,3],[4,5,6],[7,8,9]]

 

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m <= 50
• 1 <= n <= 50
• -1000 <= grid[i][j] <= 1000
• 0 <= k <= 100

 

2차원 배열을 k만큼 밀어낸 결과값을 반환하는 문제

 

Solution:

/**
 * @param {number[][]} grid
 * @param {number} k
 * @return {number[][]}
 */
var shiftGrid = function (grid, k) {
    const nums = grid[0].length;
    let shiftStr = grid.reduce(function (acc, cur) {
        return acc.concat(cur);
    });
    for (let i = 0; i < k; i++) {
        shiftStr.unshift(shiftStr.pop());
    }
    function division(data = [], size = 1) {
        const items = [...data];
        const arr = [];

        while (items.length) {
            arr.push(items.splice(0, size));
        }

        return arr;
    }
    return division(shiftStr, nums);
};

• 2차원 배열을 1차원 배열로 합친 뒤에 for문을 통해 k만큼 pop - unshift 반복
• grid[0]의 길이만큼 다시 나눠서 2차원 배열로 반환

 

Add Digits

Given an integer num, repeatedly add all its digits until the result has only one digit, and return it.

 

Example 1:

Input: num = 38
Output: 2
Explanation: The process is
38 --> 3 + 8 --> 11
11 --> 1 + 1 --> 2 
Since 2 has only one digit, return it.

Example 2:

Input: num = 0
Output: 0

 

Constraints:

• 0 <= num <= 231 - 1

 

임의의 정수를 쪼개서 각 값을 더함(sum이라고 가정)

sum을 쪼갤 수 없을 때까지 (== 한 자리 정수가 될 때까지) 실행하고 sum 반환

 

Solution:

/**
 * @param {number} num
 * @return {number}
 */
var addDigits = function (num) {
    function sumDigits(num) {
        const numStr = String(num).split("");
        let sum = numStr.reduce((a, b) => parseInt(a) + parseInt(b));
        return sum > 9 ? sumDigits(sum) : sum;
    }
    return sumDigits(num);
};

• num을 문자열로 변환하고 쪼개서 배열로 만든다.
• reduce()로 각 자리값을 더하고 sum이 두 자리면 재귀 호출, 아니면 sum 반환

 

Append K Integers With Minimal Sum

You are given an integer array nums and an integer k. Append k unique positive integers that do not appear in nums to nums such that the resulting total sum is minimum.

Return the sum of the k integers appended to nums.

 

Example 1:

Input: nums = [1,4,25,10,25], k = 2
Output: 5
Explanation: The two unique positive integers that do not appear in nums which we append are 2 and 3.
The resulting sum of nums is 1 + 4 + 25 + 10 + 25 + 2 + 3 = 70, which is the minimum.
The sum of the two integers appended is 2 + 3 = 5, so we return 5.

Example 2:

Input: nums = [5,6], k = 6
Output: 25
Explanation: The six unique positive integers that do not appear in nums which we append are 1, 2, 3, 4, 7, and 8.
The resulting sum of nums is 5 + 6 + 1 + 2 + 3 + 4 + 7 + 8 = 36, which is the minimum. 
The sum of the six integers appended is 1 + 2 + 3 + 4 + 7 + 8 = 25, so we return 25.

 

Constraints:

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

 

주어진 배열에 추가되어 최소 합을 만들어낼 k개의 나타나지 않은 숫자를 구하고
해당 숫자들의 총합을 리턴

 

Solution:

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var minimalKSum = function (nums, k) {
    let sum = 0;
    let cur = 1;
    let max = Math.max(...nums);
    nums = new Set(nums);
    while (k) {
        if (cur > max || !nums.has(cur)) {
            k--;
            sum += cur;
        }
        cur++;
    }
    return sum;
};

• 통과 X 효율성 문제

 

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
const minimalKSum = (nums, k) => {
    let remain = k;
    let index = 0;
    let sum = 0;
    nums.sort((n1, n2) => n1 - n2);
    while (remain > 0) {
        if (index === nums.length) {
            for (let i = nums[index - 1] + 1; remain > 0; i++) {
                sum += i;
                remain--;
            }
            break;
        }
        let start = index > 0 ? nums[index - 1] + 1 : 1;
        for (let i = start; remain > 0 && i < nums[index]; i++) {
            sum += i;
            remain--;
        }
        index++;
    }
    return sum;
};

 

 

• 막혀서 답답해가지고 Discuss에서 비슷하게 접근한 답안 참고
• 통과했는데 효율 엉망인 거 같아서 찾아보니까  (n*(n+1))/2 => 이런 식으로 접근하는 트릭이 있다고 하는데 무슨 말인지 잘 모르겠어서 일단 킵해두기로 함

 

다른 사람의 풀이

var minimalKSum = function(nums, k) {
  let total = (k*(k+1))/2;
    
  nums = Array.from(new Set(nums));
  nums.sort((a,b)=>a-b); 
  for (let num of nums) {
    if (num<=k) {
      k++;
      console.log(total-1)
      total=total-num+k;
      console.log(total+1)
    }
    else
      break;
  }
  return total;
}