[Daily Coding 8]pop, shift 활용/new Array()/Array.prototype.fill()/약수의 개수/Number.isInteger(value)/조건에 따라 Boolean으로 리턴할 경우/Binary Search Tree 응용

1.pop, shift 활용

배열에서 맨 앞/ 맨 뒤 요소를 삭제해야 하고, 삭제한 요소의 값이 필요할 경우

const balancedBrackets = function (str) {
  const stack = [];
  const opener = {
    '{': '}',
    '[': ']',
    '(': ')',
  };
  const closer = '}])';

  for (let i = 0; i < str.length; i++) {
    if (str[i] in opener) {
      stack.push(str[i]);
    } else if (closer.includes(str[i])) {
      const top = stack.pop(); // stack에서 요소 삭제와 동시에 삭제한 요소를 top에 할당
      const pair = opener[top];
      if (pair !== str[i]) {
        return false;
      }
    }
  }

  return stack.length === 0;
};

2.new Array()

new Array(5) // [empty * 5]

3.Array.prototype.fill()

fill(value[, start][, end])// 이상, 미만

[5,5,5,5,5].fill(2) //[2, 2, 2, 2, 2]
new Array(7).fill(2, 0, 6) //[2, 2, 2, 2, 2, 2, empty]

4.약수의 개수

1) 약수의 개수 구하기

자연수를 소인수분해 하였을 때, 각 소인수의 지수에 1을 더한 수들을 곱한 값

// 소인수분해
12 = 2^2 + 3
// 약수의 개수
(2 + 1) * (1 + 1) = 6

2) 약수의 개수 홀수, 짝수 판별하기

제곱근이 정수 -> 약수의 개수 홀수

//소인수분해
(a^p×b^q×c^r)^2 = a^2p×b^2q×c^2r
// 약수의 개수
(2p + 1) * (2q + 1) * (2r + 1) = 홀수

5.Number.isInteger(value)

정수 판별 메서드

Number.isInteger(3/2) // false
Number.isInteger(4/2) // true

6.조건에 따라 Boolean으로 리턴할 경우 true, false 생략 가능

// stack 배열의 길이가 0이면 true, 아니면 false 리턴
return !stack.length ? true; false
return !stack.length

7.Binary Search Tree 응용

Q. 길이가 m, n이고 오름차순으로 정렬되어 있는 자연수 배열들을 입력받아 전체 요소 중 k번째 요소를 리턴해야 합니다.

// 입출력 예시
let arr1 = [1, 4, 8, 10];
let arr2 = [2, 3, 5, 9];
let result = getItemFromTwoSortedArrays(arr1, arr2, 6);
console.log(result); // --> 8

arr1 = [1, 1, 2, 10];
arr2 = [3, 3];
result = getItemFromTwoSortedArrays(arr1, arr2, 4);
console.log(result); // --> 3

// A.
// cnt: k의 절반으로 원래 각 배열에서 카운트 해야하는 개수
// leftInx, rightInx: 검사 시작 인덱스
// leftStep, rightStep: 각 배열에서 실제로 카운트하는 개수
// 배열의 길이가 다를 수 있기 때문에 cnt와 leftStep/rightStep 변수를 각각 생성

const getItemFromTwoSortedArrays = function (arr1, arr2, k) {
  let leftIdx = 0,
    rightIdx = 0;

  while (k > 0) {
    let cnt = Math.ceil(k / 2);
    let leftStep = cnt,
      rightStep = cnt;

    // 엣지 케이스1
    // 카운트가 남았음에도 배열의 끝에 도달하면 k를 나머지 배열 쪽으로 넘김
    if (leftIdx === arr1.length) {
      rightIdx = rightIdx + k;
      break;
    }

    if (rightIdx === arr2.length) {
      leftIdx = leftIdx + k;
      break;
    }

    // 엣지 케이스2
    // 현재 카운트가 남아있는 후보 요소들보다 많을 경우, leftStep(현재 할당량)을 남아있는 요소들의 개수로 바꿈 -> 후에 k에서 바뀐 leftStep만큼만 빼준다
    if (cnt > arr1.length - leftIdx) leftStep = arr1.length - leftIdx;
    if (cnt > arr2.length - rightIdx) rightStep = arr2.length - rightIdx;

    // 두 배열의 현재 검사 요소 위치를 비교해서, 그 값이 작은 배열은 비교한 위치 앞에 있는 요소들을 모두 후보군에서 제외
    if (arr1[leftIdx + leftStep - 1] < arr2[rightIdx + rightStep - 1]) {
      leftIdx = leftIdx + leftStep;
      k = k - leftStep;
    } else {
      rightIdx = rightIdx + rightStep;
      k = k - rightStep;
    }
  }

  leftMax = arr1[leftIdx - 1] || -1;
  rightMax = arr2[rightIdx - 1] || -1;

  return Math.max(leftMax, rightMax);
};