Leetcode JS 30days challenge

리트코드 자바스크립트 30일 챌린지

Day 7 - 30 Days of LC JavaScript Challenge - LeetCode Discuss

자바스크립트 30일 챌린지에 참여합니다.

직접 푼 답안과 리팩토링한 답안을 공유할 예정입니다.

풀지 못한 문제는 참고한 답안을 공유하고 추후 다시 직접 풀어볼 예정입니다.

1일차 2667. Create Hello World Function

hello world라는 텍스트를 리턴하는 함수를 만드는 문제입니다.

Create Hello World Function - LeetCode

var createHelloWorld = function() {
    return function(...args) {
        return "Hello World";
    }
};

똑같이 풀었는데 아래 사람은 100%, 100%의 성능이 나왔습니다.

2일차 2620. Counter

호출할 때마다 인자로 받은 숫자를 증가시키고 그 숫자를 리턴하는 함수를 작성하는 문제입니다.

클로저를 이용하여 풀었습니다.

Counter - LeetCode

var createCounter = function(n) {
    let value = n;
    return function() {
        return value++;
    };
};

3일차 2665. Counter II

2일차의 카운터가 증가만 했다면 이제는 감소, 리셋까지 할 수 있는 카운터를 작성하는 문제입니다.

Counter II - LeetCode

var createCounter = function(init) {
    let answer = init;

    return {
        increment: () => ++answer,
        decrement: () => --answer,
        reset: () => answer = init,
    }
};

4일차 2635. Apply Transform Over Each Element in Array

배열의 모든 element에 인자로 전달받은 fn를 적용시키는 함수를 만드는 문제입니다.

Apply Transform Over Each Element in Array - LeetCode

var map = function (arr, fn) {
  return arr.map((item, idx) => {
    return fn(item, idx);
  });
  
};

간단히 for 문을 돌리는 것이 시간 복잡도가 더 낮았습니다.

5일차 2634. Filter Elements from Array

인자로 받는 fn에 해당하는 arr의 요소만 리턴하는 함수를 짜는 문제입니다.

저는 간단히 forEach를 사용하여 fn의 리턴값이 truthy한 값만 리턴하도록 코드를 짰습니다.

Filter Elements from Array - LeetCode

var filter = function (arr, fn) {
  const answer = [];
  arr.forEach((item, idx) => fn(item, idx) && answer.push(item));
  return answer;
};

6일차 2626. Array Reduce Transformation

자바스크립트 내장 메서드 Reduce를 사용하지 않고 Reduce와 같은 동작을 하는 함수를 만드는 문제였습니다.

저는 간단히 forEach를 대신 사용하여 문제를 풀었습니다.

결과값이 되어줄 변수 result의 초기값으로 init값을 넣고, result를 fn을 통해 리턴받은 값으로 업데이트를 해주었습니다.

Array Reduce Transformation - LeetCode

var reduce = function (nums, fn, init) {
  let result = init;
  nums.forEach((item, idx) => {
    result = fn(result, item);
  });

  return result;
};

정답을 맞추긴 했지만 꽤나 아쉬운 성능을 보입니다.

7일차 2629. Function Composition

functions 배열로 받은 함수들 중에 오른쪽 함수부터 순차적으로 실행하여 결과값을 리턴하는 함수를 작성하는 문제입니다.

저는 간단하게 배열의 pop을 이용하여 오른쪽에서부터 함수를 꺼내어 인자값을 넣고, 해당 값을 다시 그 다음 pop하여 가져온 함수의 인자로 넣어서 결과를 도출하는 방식으로 접근하여 문제를 풀었습니다.

Function Composition - LeetCode

var compose = function (functions) {
  return function (x) {
    let result = x;
    while (functions.length) {
      const func = functions.pop();
      result = func(result);
    }
    return result;
  };
};

8일차 2666. Allow One Function Call

인자로 받은 fn을 호출한 결과값을 한 번만 리턴하는 함수를 작성하는 문제입니다.

저는 클로져를 이용하여 isCalled가 false일 때만 원하는 동작을 수행하는 함수를 리턴하도록 코드를 작성하였습니다.

이 문제는 제가 모 스타트업의 입사 테스트 시 질문 받았던 문제이기도 합니다.

Allow One Function Call - LeetCode

var once = function (fn) {
  let isCalled = false;
  return function (...args) {
    if (isCalled) return;
    isCalled = true;
    return fn(...args);
  };
};

9일차 2623. Memoize

드디어 미디엄 문제가 등장했습니다 ㅎㅎ

인자로 받은 함수를 이용하여 진행한 계산은 다시 수행하지 않도록 memoize된 함수를 리턴하는 문제입니다.

Map을 이용하여 이미 연산을 수행한 인자들을 키값으로 넣고, 그 결과 값을 밸류값으로 넣은 뒤 인자를 받았을 때 Map에 해당 키를 가지고 있는지를 확인하여 있으면 해당 밸류를 리턴하는 방식으로 문제를 풀었습니다.

여기서 처음에 잘못했던 부분은, sum의 경우 5+5도 10이고 4+6도 10인데 처음에는 키값을 두 인자를 더 한 값으로 넣어버렸기 때문에 오류가 났습니다. 키값의 형태를 `${args[0]}_${args[1]}` 로 바꾸어 에러를 해결했습니다.

Memoize - LeetCode

function memoize(fn) {
  const cache = new Map();

  return function (...args) {
    const key = args.length > 1 ? `${args[0]}_${args[1]}` : args[0];
    if (cache.has(key)) return cache.get(key);

    const result = fn(...args);
    cache.set(key, result);
    return result;
  };
}

10일차 2632. Curry

커링함수를 구현하는 문제입니다.

인자로 들어가는 function의 length가 정해져있지 않으므로 다중-인수를 허용하는 “고급” 커리를 구현하는 방식으로 문제를 풀어야 합니다.

저는 아래 링크를 참조하여 문제를 해결했습니다.

커링

Curry - LeetCode

var curry = function (fn) {
  return function curried(...args) {
    if (args.length >= fn.length) {
      return fn.apply(this, args);
    }

    return function (...args2) {
      // args 갯수를 충족할 때까지 함수를 return
      return curried.apply(this, args.concat(args2));
    };
  };
};

11일차 2621. Sleep

인자로 넘긴 숫자만큼의 밀리세컨즈가 지난 후에 then으로 연결된 동작을 수행하도록 하는 sleep함수를 작성하는 문제입니다.

프로미스를 사용할 수 있는지 물어보는 문제였습니다.

Sleep - LeetCode

async function sleep(millis) {
  return new Promise((resolve, reject) => {
    setTimeout(function () {
      resolve();
    }, millis);
  });
}

Detailed explanation. Important question. - Sleep - LeetCode

더 간결한 답안을 찾았습니다.

async function sleep(millis) {
    await new Promise(resolve => setTimeout(resolve, millis));
}

비동기 함수는 반드시 프로미스를 리턴하기 때문에 리턴대신 await 키워드를 사용해도 됩니다.

12일차 2637. Promise Time Limit

프로미스 함수에 타임리밋을 설정하고, 해당 리밋을 초과하는 시간을 받으면 리밋으로 설정한 시간 뒤에 “Time Limit Exceeded”라는 에러 메시지를 리턴하는 고차함수를 만드는 문제입니다.

타임리밋안에 함수가 실행되어야만 하므로, 타임리밋이 지나면 reject하는 setTimeout 코드를 작성하는 방식으로 문제를 풀었습니다.

Promise Time Limit - LeetCode

var timeLimit = function (fn, t) {
  return async function (...args) {
    return new Promise((resolve, reject) => {
      setTimeout(() => {
        reject("Time Limit Exceeded");
      }, t);
      fn(...args).then(resolve, reject);
    });
  };
};

이 문제는 또한 Promise.race를 사용하여 풀 수도 있습니다.

원래 시행하고자 하는 인자로 받는 프라미스 함수와 일정 시간이 지난 뒤 reject하는 프라미스 함수 두 개를 Promise.race를 통해 리턴하면 둘 중 먼저 완료된 결과값을 리턴하기 때문에 문제에서 요구하는 조건에 맞는 결과를 냅니다.

Easy Promise race solution - Promise Time Limit - LeetCode

var timeLimit = function (fn, t) {
  return async function (...args) {
    const originalFnPromise = fn(...args);

    const timeoutPromise = new Promise((_, reject) => {
      setTimeout(() => {
        reject("Time Limit Exceeded");
      }, t);
    });

    return Promise.race([originalFnPromise, timeoutPromise]);
  };
};

13일차 2636. Promise Pool

Promise.all을 쓸 수 있는지를 물어보는 문제였습니다.

인자로 받은 n개 만큼 Promise.all로 묶어서 함수를 실행하고, 그 다음 함수들은 recursion으로 하나씩 마저 실행해주면 됩니다.

Promise Pool - LeetCode

var promisePool = async function (functions, n) {
  let i = 0;

  const next = async () => {
    const fn = functions[i++];
    if (!fn) return;
    await fn();
    return next();
  };
  return await Promise.all(Array(n).fill().map(next));
};

14일차 2622. Cache With Time Limit

TimeLimitedCache 에 일정 시간이 지나면 사라지는 키, 밸류를 세팅하는 문제였습니다.

setTimeout을 이용하면 되는 간단한 문제이지만 처음 풀었을 때는 이미 존재하는 키에 새로운 값을 덮어씌울 경우 clearTimeout하는 것을 놓쳐서 오답이 나왔었습니다.

Map을 사용했다면 더 좋은 시간복잡도를 얻을 수 있을 것입니다.

Cache With Time Limit - LeetCode

var TimeLimitedCache = function () {};

/**
 * @param {number} key
 * @param {number} value
 * @param {number} time until expiration in ms
 * @return {boolean} if un-expired key already existed
 */
TimeLimitedCache.prototype.set = function (key, value, duration) {
  let isAlreadyExist = false;
  if (this[key]) {
    isAlreadyExist = true;
    // clearTimeout을 안 하면 전의 key에 설정되어있던 setTimeout이 취소되지 않아서 오답이 나옴
    clearTimeout(this[key].timeOutId);
  }

  const timeOutId = setTimeout(() => {
    delete this[key];
  }, duration);
  this[key] = { value, timeOutId };

  return isAlreadyExist;
};

/**
 * @param {number} key
 * @return {number} value associated with key
 */
TimeLimitedCache.prototype.get = function (key) {
  return this[key]?.value ?? -1;
};

/**
 * @return {number} count of non-expired keys
 */
TimeLimitedCache.prototype.count = function () {
  return Object.keys(this).length;
};

15일차 2627. Debounce

13일차와 비슷한문제입니다. 유명한 디바운스 문제로, 일정 시간동안 연속적인 함수 실행을 막는 코드를 짜는 문제입니다. 마찬가지로 셋타임아웃을 이용하여 문제를 풀었습니다.

Debounce - LeetCode

var debounce = function (fn, t) {
  let timerId;
  return function (...args) {
    clearTimeout(timerId);
    timerId = setTimeout(() => {
      fn(...args);
    }, t);
  };
};

16일차 2676. Throttle

쓰로틀을 작성하는 문제입니다.

처음으로 실행하는 함수는 무조건 실행하고, 시간제한이 지나기 전까지 함수들의 실행을 무시하다가 마지막 함수 실행을 일정시간이 지나면 진행하는 코드를 작성해야 합니다.

따라서 savedArgs라는 변수를 만들어 쓰로틀 시간 제한이 아직 지나지 않았을 때 인자를 받아서 덮어씌워두고, 쓰로틀 시간이 지나면 즉시 마지막으로 저장된 인자를 실행하는 방식으로 코드를 작성했습니다.

저는 아래 링크를 참조하여 문제를 풀었습니다.

Throttle - LeetCode

var throttle = function (fn, t) {
  let isThrottled = false;
  let savedArgs = null;

  return function (...args) {
    if (isThrottled) {
      // wait for the next call
      savedArgs = args;
      return;
    }
    // execute the function for the first time
    fn(...args);
    isThrottled = true;
    setTimeout(helper, t);

    function helper() {
      if (savedArgs) {
        fn(...savedArgs);
        isThrottled = true;
        savedArgs = null;
        setTimeout(helper, t);
        return;
      }
      isThrottled = false;
    }
  };
};

17일차 2628. JSON Deep Equal

깊은 비교를 직접 구현하는 문제입니다. recursion과 타입비교를 잘 작성하면 되는 문제였습니다.

JSON Deep Equal - LeetCode

저는 풀다가 코드가 너무 지저분해지고 시간 소요가 많이 되어서 아래 링크를 참고했습니다.

All Cases Detailed explanation! - JSON Deep Equal - LeetCode

var areDeeplyEqual = function(o1, o2) {
    // All equal values and same objects are eliminated
    if (o1 === o2) return true;
    
    // If any of o1 or o2 is not an object, they are different values
    if (typeof o1 != 'object' || typeof o2 != 'object') return false;

    // Both of them should be objects or arrays
    if (Array.isArray(o1) !== Array.isArray(o2)) return false;
    
    // Both should have same keys, in case of indexes this will return indexes
    if (Object.keys(o1).length != Object.keys(o2).length) return false;

    // Check if all values against keys of o1 and o2 are deeply equal.
    // If number of keys are same, then at a different key in objects would mean at least
    // 1 value against the key of o2 will be undefined
    for (const key in o1) {
        if (!areDeeplyEqual(o1[key], o2[key])) return false;
    }

    // All checks passed
    return true;
};

18일차 2633. Convert Object to JSON String

17일차 문제와 유사하게 recursion과 타입체크를 이용하여 JSON 오브젝트를 스트링으로 변환하는 문제입니다.

문제 풀이에 아래 링크를 참고했습니다.

Without using the built-in JSON.stringify method | Recursive solution - Convert Object to JSON…

Convert Object to JSON String - LeetCode

var jsonStringify = function (object) {
  if (object === null) return "null";
  // return the string value surrounded by double quotes.
  if (typeof object === "string") return `"${object}"`;
  // return its string representation.
  if (typeof object === "number" || typeof object === "boolean") {
    return String(object);
  }

  // Recursively convert each item to a JSON string suing map and join them with commas.
  if (Array.isArray(object)) {
    const items = object.map((item) => jsonStringify(item)).join(",");
    return `[${items}]`;
  }
  // Recursively convert each value to a JSON string and pair it with the corresponding key.
  if (typeof object === "object") {
    const keys = Object.keys(object);
    const items = keys.map((key) => `"${key}":${jsonStringify(object[key])}`);
    return `{${items.join(",")}}`;
  }
};

19일차 2675. Array of Objects to Matrix

nested object를 recursion을 사용하여 원하는 답변을 얻는 문제입니다.

저는 아래 링크를 참고하여 문제풀이를 하였습니다.

undefined - Array of Objects to Matrix - LeetCode

Array of Objects to Matrix - LeetCode

function flattenObj(obj, parent, res = {}) {
  for (let key in obj) {
    const propName = parent ? parent + "." + key : key;
    if (typeof obj[key] == "object" && obj[key] !== null) {
      flattenObj(obj[key], propName, res);
    } else {
      res[propName] = obj[key];
    }
  }
  return res;
}

var jsonToMatrix = function (arr) {
  const keys = [];
  const flat = arr.map((item) => flattenObj(item));

  for (let item of flat) {
    for (let key of Object.keys(item)) {
      if (!keys.includes(key)) {
        keys.push(key);
      }
    }
  }

  keys.sort();

  const res = [keys];
  for (let item of flat) {
    const row = [];
    for (let key of keys) {
      if (key in item) row.push(item[key]);
      else row.push("");
    }
    res.push(row);
  }
  return res;
};

20일차 2700. Differences Between Two Objects

Differences Between Two Objects - LeetCode

아래 링크를 참고하여 풀었습니다.

undefined - Differences Between Two Objects - LeetCode

const objDiff = (sourceObj, targetObj) => {
  // Special case: Objects are the same or values are same
  if (sourceObj === targetObj) {
    return null;
  }

  // Special cases: Null values or different types
  if (sourceObj === null || targetObj === null) {
    return [sourceObj, targetObj];
  }

  if (typeof sourceObj !== "object" || typeof targetObj !== "object") {
    return [sourceObj, targetObj];
  }

  if (Array.isArray(sourceObj) !== Array.isArray(targetObj)) {
    return [sourceObj, targetObj];
  }

  const diffObj = {}; // Object to store the differences

  // Iterate over the keys in sourceObj
  Object.keys(sourceObj).forEach((key) => {
    if (key in targetObj) {
      const subDiff = objDiff(sourceObj[key], targetObj[key]); // Recursive call for nested objects

      // If there are differences, add them to the diffObj
      if (subDiff === null) return;
      if (Object.keys(subDiff).length > 0) {
        diffObj[key] = subDiff;
      }
    }
  });

  return diffObj; // Return the object containing the differences
};

21일차 2677. Chunk Array

인자로 받은 숫자만큼 배열을 쪼개어 리턴하는 함수를 만드는 문제입니다.

Chunk Array - LeetCode

var chunk = function (arr, size) {
  if (!arr.length) return [];
  if (size >= arr.length) return [arr];
  const answer = [];

  let tempArr = [];
  arr.forEach((item, idx) => {
    tempArr.push(item);
    if ((idx + 1) % size === 0) {
      answer.push([...tempArr]);
      tempArr = [];
    }
  });

  if (tempArr.length) answer.push(tempArr);

  return answer;
};

22일차 2625. Flatten Deeply Nested Array

주어진 n만큼의 depth만큼만 array를 flat하게 만드는 함수를 작성하는 문제입니다. 지난 며칠 문제들과 마찬가지로 재귀를 이용하여 문제를 풀었습니다.

Flatten Deeply Nested Array - LeetCode

var flat = function (arr, n) {
  if (n === 0) return arr;
  const answer = [];

  const checkArr = (array, depth) => {
    array.forEach((item) => {
      if (!Array.isArray(item) && depth <= n) {
        answer.push(item);
        return;
      }

      if (Array.isArray(item)) {
        if (depth >= n) {
          answer.push(item);
        } else {
          checkArr(item, depth + 1);
        }
      }
    });
  };

  checkArr(arr, 0);
  return answer;
};

23일차 2619. Array Prototype Last

this의 마지막 element를 리턴하는 last 메서드를 짜는 문제입니다.

this[this.length-1]을 할 수 있는지를 묻는 문제였습니다.

Array Prototype Last - LeetCode

Array.prototype.last = function () {
  return this[this.length - 1] ?? -1;
};

24일차 2631. Group By

배열을 순회하며 인자로 전달받은 함수를 실행한 값을 키값으로 갖는 오브젝트를 리턴하는 groupBy라는 메서드를 프로토타입에 만드는 문제였습니다.

this를 통해 배열에 접근할 수 있는지,

이미 같은 값의 키가 존재하는지를 확인하고 존재한다면 값을 해당 배열에 push할 수 있는지를 물어보는 문제였습니다.

Group By - LeetCode

Array.prototype.groupBy = function (fn) {
  const answer = {};

  this.forEach((item) => {
    const key = fn(item);
    if (answer[key]) {
      answer[key].push(item);
    } else {
      answer[key] = [item];
    }
  });

  return answer;
};

25일차 2618. Check if Object Instance of Class

인자로 받은 object가 인자로 받은 class의 인스턴스인지를 확인하는 문제입니다.

while문을 돌며 객체의 프로토타입을 타고 올라가면서 해당 프로토타입과 클래스를 비교해야합니다.

저는 아래 링크를 참고해서 문제를 풀었습니다.

Javascript Solution With Explaination | Easy to Understand - Check if Object Instance of Class …

Check if Object Instance of Class - LeetCode

var checkIfInstanceOf = function (obj, classFunction) {
  while (obj !== null && obj !== undefined) {
    if (obj.constructor === classFunction) return true;

    obj = Object.getPrototypeOf(obj);
  }

  return false;
};

26일차 2693. Call Function with Custom Context

this.call을 이용하지 않고 인자로 받은 함수와 context를 연결하여 함수에서호출할 수 있도록 Function prototype에 callPolyfill이라는 함수를 만드는 문제입니다.

프로토타입 내부에 새로운 함수를 하나 만든 뒤, 해당 함수에 컨텍스트와 인자를 바인드 한 다음 호출하는 방식으로 문제를 풀었습니다.

문제해결에 아래 링크를 참고했습니다.

How to call self prototype function in javascript object Constructor

Call Function with Custom Context - LeetCode

Function.prototype.callPolyfill = function (context, ...args) {
  this.callFn = this.bind(context, ...args);
  return this.callFn();
};

27일차 2694. Event Emitter

EventEmitter라는 클래스에 subscribe를 할 때마다 event를 키값으로 하고 value 값을 인자로 받은 cb로 하는 this.events 객체를 만들고

unsubscribe시 이벤트 콜백 배열을 선입선출로 제거한 뒤

emit 시 callback에 args 인자를 넘겨 그 결과를 배열에 담아 리턴하는 코드를 짜는 문제였습니다.

Event Emitter - LeetCode

class EventEmitter {
  constructor() {
    this.events = {};
  }

  subscribe(event, cb) {
    if (!this.events[event]) this.events[event] = [cb];
    else this.events[event] = [...this.events[event], cb];

    return {
      unsubscribe: () => {
        this.events[event] = this.events[event].slice(1);
        return undefined;
      },
    };
  }

  emit(event, args = []) {
    if (!this.events[event]) return [];
    return this.events[event].map((cb) => cb(...args));
  }
}

28일차 2695. Array Wrapper

ArrayWrapper라는 객체의 프로토타입에 문제에서 요구한 기능을 하는 메서드를 작성하는 문제입니다.

Number와 String primitive 타입에 valueOf라는 메서드가 있는 걸 알려주기위해 만든 문제로 보입니다.

Number.prototype.valueOf() - JavaScript | MDN

String.prototype.valueOf() - JavaScript | MDN

Array Wrapper - LeetCode

var ArrayWrapper = function (nums) {
  this.arr = nums;
};

ArrayWrapper.prototype.valueOf = function () {
  this.value = this.arr.reduce((acc, cur) => acc + cur, 0);
  return this.value;
};

ArrayWrapper.prototype.toString = function () {
  return `[${this.arr.join(",")}]`;
};

29일차 2648. Generate Fibonacci Sequence

제너레이터를 이용하여 피보나치 함수를 구현하는 문제였습니다.

Generate Fibonacci Sequence - LeetCode

var fibGenerator = function* () {
  let idx = 0;
  const value = [0, 1, 1, 2, 3];

  while (true) {
    if (idx < 4) yield value[idx++];
    if (!value[idx]) {
      value[idx] = value[idx - 1] + value[idx - 2];
    }
    yield value[idx];
    idx++;
  }
};

30일차 2649. Nested Array Generator

배열을 순회하며 배열의 인자가 숫자면 yield하고 배열일 경우 값이 숫자타입이 나올 때까지recursion으로 순회하는 코드를 작성하는 문제입니다.

recursion을 이용해야하는 다른 비슷한 문제의 경우 helper 함수를 별도로 작성하여 문제를 푸는 방식을 많이 사용하였는데

이번 문제의 경우 generator함수를 작성하는 것이기 때문에 helper함수 없이 자체 함수로 recursion 하여 답을 구할 수 있습니다.

Nested Array Generator - LeetCode

var inorderTraversal = function* (arr) {
    if(!Array.isArray(arr)) {
        yield arr
        return
    }

    for(let i = 0; i < arr.length; i++) {
        yield* inorderTraversal(arr[i])
    }
};