30 Days of JavaScript - JSON | LeetCode

문제를 풀면서 문제의 의도와 연관된 개념에 대해 정리합니다.

2727. Is Object Empty

JSON.parse의 결과로 주어지는 객체 또는 배열이 비어 있는지 시간 복잡도 O(1)로 판단하기

• JSON.stringify를 이용한 풀이는 O(n)

  • 객체의 모든 키와 값, 배열의 모든 요소를 순회하면서 문자열로 변환하기 때문에 시간 복잡도 O(n)

• for in 이용한 풀이

  function isEmpty(obj: Obj): boolean {
      for(const _ in obj) {
          return false;
      }
  
      return true;
  };

  • for in문은 enumerable 속성만 순회하므로 빈 객체인 경우 반복문이 실행되지 않음
    • enumerable: 반복문에서 열거 가능 여부를 결정하는 attribute
  • enumerable: false 인 속성만 존재하는 경우 for in문을 순회하지 않음
    • enumerable: false 인 속성만 존재한다면 비어있는 것처럼 보이는 것이지 실제로는 속성이 존재함
    • enumerable: false 인 속성은 언제 사용하지?
      • 객체 내부에서만 사용하고, 외부에서 노출하고 싶지 않은 데이터 저장용(예: 클래스 내부 상태, 캐시)
      • 라이브러리나 프레임워크 내부에서 상태를 저장하면서 표준 객체 반복 동작을 방해하지 않기 위해(예: React의 내부 Fiber 객체)

2677. Chunk Array

배열을 일정한 크기로 잘라 새로운 2차원 배열로 만들기

• 순차적으로 배열 처리하기
  • 배열을 앞에서부터 일정한 크기만큼 묶고, 잘라서, 새 배열로 데이터 변환하기
• 엣지 케이스 처리하기
  • size가 배열보다 클 때
  • 배열이 비어있을 때
  • 마지막 청크가 size보다 작을 때
• 시간 복잡도 O(n)으로 한 번 순회로 해결하기

2619. Array Prototype Last

JavaScript 프로토타입 확장 이해하기

• 모든 배열에 last 메서드 추가하기
  • 모든 배열 인스턴스가 공통으로 사용하는 프로토타입 객체에 메서드를 추가하여 기능 확장
• this 바인딩에 대한 이해
  • 메서드 내부에서 this가 호출된 배열 자체로 바인딩된다는 점 활용
  • 단, 화살표 함수 사용 시 this가 배열을 가리키지 않음
• 엣지 케이스 처리
  • 배열이 비어있는 경우, -1 반환

2631. Group By

groupBy 직접 구현하기

• 프로토타입 확장하여 Array에 사용자 정의 메서드 정의
• 고차 함수 활용
  • fn(item)의 반환 값을 key로 사용
  • 키에 해당하는 요소를 push
• 그룹 연산 알고리즘 이해
• 시간 복잡도 O(n)으로 처리

2724. Sort By

배열을 fn이 반환하는 숫자값을 기준으로 배열을 정렬하기

• 정렬 기준을 함수로 추상화하여 전달받는 패턴 익히기
  • 고차함수 사용하는 패턴

2722. Join Two Arrays by ID

두 개의 객체 배열을 id 기반으로 병합하기

• 같은 id를 가진 객체를 하나로 합치는 병합 로직 구현
  • id 같은 객체가 존재한다면 arr2가 arr1을 override
• 성능 고려
  • 배열의 JSON 문자열 길이가 최대 10^6으로 단순 이중 반복으로 비교 시 시간 복잡도 O(n*m)으로 시간초과 발생할 수 있음
  • findIndex로 풀었다가 시간 초과 발생함
    • findIndex + sort ⇒ O(n*m) + O(k log k)
  • Map 객체로 풀이 변경
    • Map.has + sort ⇒ O(n + m + k log k)
• 결과 반환 시 배열은 id 기준으로 정렬

2625. Flatten Deeply Nested Array

Array.flat 메서드 직접 구현하기

• n레벨까지 flatten 처리

  • depth < n 일 때만 flatten 처리해야한다는 규칙에 대한 이해

• 시간 복잡도 O(n) 고려

  • 재귀로 처리할 경우, 1000 ~ 2000 depth에서 stack overflow가 발생할 수 있음 ⇒ 재귀로 풀었는데, maxDepth가 1000이어서 통과하긴 함
  • DFS/BFS 또는 stack으로 풀기

• TypeScript + stack 으로 풀 때 타입 에러

  • const stack = arr.map(item => [item, 0]); 의 타입이 의도한대로 추론되지 않음
    • 의도한 타입: type StackElement = [MultiDimensionalArray, number]
    • 추론된 타입: type StackElement = Array<number | MultiDimensionalArray>
    • 다음과 같이 타입 단언하여 해결

      var flat = function (arr:  MultiDimensionalArray, n: number):  MultiDimensionalArray {
        if(n === 0) return arr;
  
        const result = [];
        const stack = arr.map(item => [item, 0]).reverse();
  
        while (stack.length > 0) {
          const stackElement = stack.pop();
          const item = stackElement[0] as MultiDimensionalArray;
          const depth = stackElement[1] as number;
  
          if (Array.isArray(item) && depth < n) {
            for(let index = item.length - 1; index >= 0; index -= 1){
              stack.push([item[index], depth + 1])    
            }
          } else {
            result.push(item);
          }
        }

2705. Compact Object

• JSON.parse 결과물 활용 여부
  • 입력 구조가 객체(Object), 배열(Array), 숫자(Number), 문자열(String), 불리언(Boolean), null로만 구성됨
• 깊은 구조까지 모든 falsy 값 제거
  • 중첩 객체/배열에 대해 재귀적으로 처리
    • 객체: falsy key delete 처리, truthy key만 유지
    • 배열: truthy 요소만 push
• 시간 복잡도 O(n)으로 구조 전체를 정규화 하기