[LeetCode] Kth Missing Positive Number

1.문제

Given an array arr of positive integers sorted in a strictly increasing order, and an integer k.

Return the kth positive integer that is missing from this array.

오름차순으로 정렬되어있는 정수 배열 arr 이 주어지고 양수 k가 주어질 때 arr에 있지 않는 숫자들 중 k 번째에 있는 숫자를 리턴하는 문제이다.

Example 1

Input: arr = [2,3,4,7,11], k = 5
Output: 9
Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5th missing positive integer is 9.

Example 2

Input: arr = [1,2,3,4], k = 2
Output: 6
Explanation: The missing positive integers are [5,6,7,...]. The 2nd missing positive integer is 6.

Constraints:

• 1 <= arr.length <= 1000
• 1 <= arr[i] <= 1000
• 1 <= k <= 1000
• arr[i] < arr[j] for 1 <= i < j <= arr.length

2.풀이

1. arr에 존재 하지 않는 숫자를 1부터 missing 배열에 missing 배열의 길이가 k가 될때까지 넣는다.
2. missing 배열의 가장 마지막 값을 리턴한다.

/**
 * @param {number[]} arr
 * @param {number} k
 * @return {number}
 */
const findKthPositive = function (arr, k) {
  const missing = [];
  let i = 1;

  while (missing.length < k) {
    // arr 에 들어있지 않는 숫자를 missing 배열에 저장한다.
    if (!arr.includes(i)) {
      missing.push(i);
    }
    i++;
  }

  // missing 배열에서 최대값을 리턴해준다.
  return missing[missing.length - 1];
};

3.결과