Portfolio

💡

WEEK

16-4

16-6

재영

WEEK 3 - 7번 문제


const CompositeRomans = {
    IV: 4,
    IX: 9,
    XL: 40,
    XC: 90,
    CD: 400,
    CM: 900
}

const Romans = {
    I: 1,
    V: 5,
    X: 10,
    L: 50,
    C: 100,
    D: 500,
    M: 1000
}

/**
 * @param {string} s
 * @return {number}
 */
var romanToInt = function(s) {
    let result = 0;

    let i = 0;

    while (i < s.length) {
        const now = s[i];

        if (i + 1 < s.length) {
            const next = s[i + 1];
            const compositeRoman = now + next;

            if (compositeRoman in CompositeRomans) {
                result += CompositeRomans[compositeRoman];
                
                i += 2;
                continue;
            }
        }

        result += Romans[now]

        i += 1;
    }

    return result;
};

WEEK 3 - 8번 문제


/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var backspaceCompare = function(s, t) {
    const getIndex = (s, index) => {
        let backspaceCount = 0;
        let i = index;

        while (i >= 0) {
            if (s[i] === "#") {
                backspaceCount += 1;
                i -= 1;
                continue;
            }

            else if (backspaceCount > 0) {
                backspaceCount -= 1;
                i -= 1;
                continue;
            }

            else {
                break;
            }
        }

        return i;
    }

    let endS = s.length - 1;
    let endT = t.length - 1;

    let flag = true;

    while (endS >= 0 || endT >= 0) {
        endS = getIndex(s, endS);
        endT = getIndex(t, endT);
        
        if (endS < 0 && endT < 0) {
            break;
        }

        if (endS < 0 || endT < 0) {
            flag = false;
            break;
        }

        if (s[endS] !== t[endT]) {
            flag = false;
            break;
        }

        endS -= 1;
        endT -= 1;
    }

    return flag;
};

WEEK 4 - 1번 문제


/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function(p, q) {
    if (!p && !q) return true;

    if (p?.val !== q?.val) return false;

    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};

WEEK 4 - 2번 문제


/**
 * @param {number} n
 * @return {number}
 */
var hammingWeight = function (n) {
  let cnt = 0;

  while (n > 0) {
    if (n & 1) {
      cnt += 1;
    }

    n >>= 1;
  }

  return cnt;
};

WEEK 4 - 3번 문제

WEEK 4 - 4번 문제


/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
    return nums.reduce((acc, cur) => acc ^ cur, 0)
};

WEEK 4- 5번 문제


/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {bool`ean}
 */
var isPalindrome = function(head) {
    /**
     * 런너 기법 실행
     * - slow: 느리게 가는 동안 뒷쪽으로 이동하는 포인터를 만들어내고, 후에 비교하기 위해 계속 나아감.
     * - fast: 반쪽으로 나뉘는 경로를 찾기 위해 slow보다 2배 더 빠르게 연결리스트를 탐색
     */
    let slow = head;
    let fast = head;

    let prev = null;
    let next = head;

    while (fast.next) {
        fast = fast.next;
        
        next = slow.next;
        
        slow.next = prev;

        prev = slow;

        slow = next;

        fast = fast.next;
        
        if (fast === null) {
            break;
        }
    }

    // 홀수일 경우에 대한 예외처리 진행
    if (fast) {
        slow = slow.next;
    }

    while (slow) {
        console.log({ slow, prev })
        if (slow.val !== prev.val) {
            return false;
        }

        slow = slow.next;
        prev = prev.next;
    }

    return true;
};

WEEK 4 - 6번 문제


/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function(nums) {
    // 임시 저장 값을 저장하는 변수를 생성한다. 이 값에는 0의 개수를 세준다.
    // 반복문을 실행한다. 이때 0을 만날 때마다 카운트를 한다.
    // 옮기는 작업을 실행한다. 0의 개수만큼 이전 인덱스에 현재의 값을 넣어줘야 한다.
    // 결과를 반환한다.

    let count = 0;

    for (let i = 0; i < nums.length; i += 1) {
        if (!nums[i]) {
            count += 1;
            continue;
        }

        if (count > 0) {
            nums[i - count] = nums[i];
            nums[i] = 0;
        }
    }

    return nums;
};

WEEK 4 - 7번 문제


/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    if (root.val === null) return true;
    if (root.left === null && root.right === null) return true;

    let flag = true;

    const dfs = (leftRoot, rightRoot) => {
        if (leftRoot === null && rightRoot === null) {
            return;
        }

        if ((leftRoot === null || rightRoot === null) || leftRoot.val !== rightRoot.val) {
            flag = false;
            return;
        }

        dfs(leftRoot.right, rightRoot.left);
        dfs(leftRoot.left, rightRoot.right);
    }

    dfs(root.left, root.right)

    return flag;
};

WEEK 4 - 8번 문제


/** * 클래스101 라이브 코딩 했던 문제
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function(nums) {
    const len = nums.length;
    return nums.reduce((acc, cur) => acc - cur, (len * (len + 1) / 2))  
};

WEEK 4 - 9번 문제


/**
 * 1분.
 */
var isPalindrome = function(x) {
    const strX = x.toString();

    let left = 0;
    let right = strX.length - 1;

    let flag = true; // 펠린드롬인지 여부

    while (left <= right) {
        if (strX[left] !== strX[right]) {
            flag = false;
            break;
        }

        left += 1;
        right -= 1;
    }

    return flag;
};

WEEK 4 - 10번 문제


/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

const dfs = (nums) => {
    if (!nums.length) return null;

    const nodeIndex = Math.floor(nums.length / 2);
    const node = new TreeNode(nums[nodeIndex]);

    node.left = dfs(nums.slice(0, nodeIndex));
    node.right = dfs(nums.slice(nodeIndex + 1));

    return node;
}

/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var sortedArrayToBST = function(nums) {
    return dfs(nums);
};

WEEK 5 - 1번 문제


// 1분

/**
 * @param {number} n - a positive integer
 * @return {number} - a positive integer
 */
var reverseBits = function(n) {
  return parseInt([...n.toString(2).padStart(32, '0')].reverse().join(""), 2);
};

WEEK 5 - 2번 문제


/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} subRoot
 * @return {boolean}
 */
var isSubtree = function(root, subRoot) {
    let flag = false; // 반환값

    const deepCheck = (node, target) => {
        if (node === null || target === null) {
            return node === target;       
        }

        if (node.val !== target.val) {
            return false;
        }

        return deepCheck(node.left, target.left) && deepCheck(node.right, target.right)
    }

    const dfs = (node) => {
        if (flag || !node) return;

        if (node.val === target.val) {
            if (deepCheck(node, target)) {
                flag = true;
            }
        }

        dfs(node.left, subRoot);
        dfs(node.right, subRoot);
    }

    dfs(root);

    return flag;
};


/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} subRoot
 * @return {boolean}
 */
var isSubtree = function(root, subRoot) {
    let flag = false; // 반환값

    const deepCheck = (node, target) => {
        if (node === null || target === null) {
            return node === target;       
        }

        if (node.val !== target.val) {
            return false;
        }

        return deepCheck(node.left, target.left) && deepCheck(node.right, target.right)
    }

    const dfs = (node) => {
        if (flag || !node) return;

        if (node.val === subRoot.val) {
            if (deepCheck(node, subRoot)) {
                flag = true;
            }
        }

        dfs(node.left);
        dfs(node.right);
    }

    dfs(root);

    return flag;
};

WEEK 5 - 3번 문제


const square = (n) => v => v ** n;
const sortByAsc = (a, b) => a - b;

/**
 * 30초
 * @param {number[]} nums
 * @return {number[]}
 */
var sortedSquares = function(nums) {
    return nums.map(square(2)).sort(sortByAsc);
};

WEEK 5 - 4번 문제


/**
 * @param {number[]} nums
 * @return {number}
 */
const maxSubArray = (nums) => {
    const dp = new Array(nums.length + 1).fill(0);
    dp[0] = -Infinity;

    nums.forEach((num, index) => {
        dp[index + 1] = Math.max(dp[index] + num, num);
    })
    
    return Math.max(...dp);
};

WEEK 5 - 5번 문제


/**
 * @param {number[][]} intervals
 * @param {number[]} newInterval
 * @return {number[][]}
 */
var insert = function (intervals, newInterval) {
  if (!intervals.length) {
    return [newInterval];
  }

  const res = [];

  const mergedInterval = [newInterval[0], newInterval[1]];
  let inserted = false;

  intervals.forEach((interval) => {
    const [start, end] = interval;

    if (end < newInterval[0] || start > newInterval[1]) { // 포개어지지 않을 때
      if (start > newInterval[1] && !inserted) { // 포개어지지 않고 아직 머지인터벌을 넣지 않았을 때 
        res.push(mergedInterval);
        inserted = true; // 머지 인터벌을 넣음.
      }

      res.push([start, end]);
      return;
    }

    // 포개어진 경우 1
    if (start < mergedInterval[0]) {
      mergedInterval[0] = start;
    }

    // 포개어진 경우 2
    if (end > mergedInterval[1]) {
      mergedInterval[1] = end;
    }
  });

  if (!inserted) {
    res.push(mergedInterval);
  }

  return res;
};ㅆ

WEEK 5 - 6번 문제


class CustomQueue {
  constructor() {
    this.queue = [];
    this.front = 0;
    this.rear = 0;
  }
  enqueue(value) {
    this.queue[this.rear++] = value;
  }
  dequeue() {
    const value = this.queue[this.front];
    delete this.queue[this.front];
    this.front += 1;
    return value;
  }
  peek() {
    return this.queue[this.front];
  }
  size() {
    return this.rear - this.front;
  }
}

const directions = [[0, -1], [0, 1], [1, 0], [-1, 0]]

/**
 * @param {number[][]} mat
 * @return {number[][]}
 */
var updateMatrix = function(mat) {
    const res = JSON.parse(JSON.stringify(mat));
    const queue = new CustomQueue();
    const visited = JSON.parse(JSON.stringify(mat));

    for (let row = 0; row < mat.length; row += 1) {
        for (let col = 0; col < mat[0].length; col += 1) {
            res[row][col] = 0;
            visited[row][col] = false;

            if (mat[row][col] === 0) {
                queue.enqueue([row, col, 0])
            }
        }
    }

    while (queue.size()) {
        const [r, c, cnt] = queue.dequeue();

        visited[r][c] = true; // visited

        for (const [dr, dc] of directions) {
            const nr = r + dr;
            const nc = c + dc;

            if (
                nr >= 0 && 
                nc >= 0 && 
                nr < mat.length && 
                nc < mat[0].length && 
                !visited[nr][nc]
            ) {
                if (mat[nr][nc] === 1) {
                    visited[nr][nc] = true;
                    res[nr][nc] = cnt + 1;
                }

                queue.enqueue([nr, nc, cnt + 1])
            }
        }
    }

    return res;
};

WEEK 5 - 7번 문제


class MinHeap {
  constructor() {
    this.heap = [null];
  }

  heappush(value) {
    this.heap.push(value);
    let nowIndex = this.heap.length - 1;
    let parentIndex = Math.floor(nowIndex / 2);
    while (nowIndex > 1 && this.heap[parentIndex][1] > this.heap[nowIndex][1]) {
      this.swap(nowIndex, parentIndex);
      nowIndex = parentIndex;
      parentIndex = Math.floor(nowIndex / 2);
    }
  }

  heappop() {
    if (this.length === 1) return this.heap.pop();
    const returnValue = this.heap[1];
    this.heap[1] = this.heap.pop();

    let nowIndex = 1;
    let leftIndex = nowIndex * 2;
    let rightIndex = nowIndex * 2 + 1;

    if (!this.heap[rightIndex]) {
      if (
        this.heap[leftIndex] &&
        this.heap[nowIndex][1] > this.heap[leftIndex][1]
      ) {
        this.swap(nowIndex, leftIndex);
        return returnValue;
      }
    }

    while (
      this.heap[rightIndex] &&
      (this.heap[nowIndex][1] > this.heap[leftIndex][1] ||
        this.heap[nowIndex][1] > this.heap[rightIndex][1])
    ) {
      if (this.heap[leftIndex][1] < this.heap[rightIndex][1]) {
        this.swap(nowIndex, leftIndex);
        nowIndex = leftIndex;
      } else {
        this.swap(nowIndex, rightIndex);
        nowIndex = rightIndex;
      }

      leftIndex = nowIndex * 2;
      rightIndex = nowIndex * 2 + 1;
    }
    return returnValue;
  }

  swap(a, b) {
    [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
  }

  get length() {
    return this.heap.length - 1;
  }
}


/**
 * @param {number[][]} points
 * @param {number} k
 * @return {number[][]}
 */
var kClosest = function(points, k) {
    const minHeap = new MinHeap();

    points.forEach(([x, y]) => {
        const dist = Math.pow(x, 2) + Math.pow(y, 2);
        minHeap.heappush([[x, y], dist]);
    })

    const res = [];

    for (let i = 0; i < k; i += 1) {
        const now = minHeap.heappop();
        res.push(now[0]);
    }

    return res;
};

WEEK 6 - 1번 문제


/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    let result = 0;

    let left = 0;  
    let right = 0;

    const set = new Set();

    while (left <= right && right < s.length) {
        const now = s[right];
        
        const beforeSize = set.size;
    
        set.add(s[right]);

        // abc -> a "사이즈가 바뀌었다" = "유니크한 값들만 있다" <= set 자체가 유니크한 값만 받기 때문에
        if (beforeSize === set.size && left !== right) {
            while (set.size === right - left) {
                set.delete(s[left]); // left가 right인 case
                set.add(s[right]); // 다시 한 번 추가
                left += 1;
            }
        }

        right += 1;

        result = Math.max(result, set.size)
    }

    return result;
};

최적화

생각해보니 set.has를 쓰면 쉽게 비교가 되더라 -_-

약 30%의 성능 최적화가 되었다. (83ms → 60ms)


/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    let result = 0;

    let left = 0;  
    let right = 0;

    const set = new Set();

    while (left <= right && right < s.length) {
        const now = s[right];
        
        while (set.has(now)) {
            set.delete(s[left]);
            left += 1;
        }

        set.add(now)
        
        right += 1;

        if (result < set.size) {
            result = set.size;
        }
    }

    return result;
};

WEEK 6 - 2번 문제


/**
 * 40분
 * @note 최적화 이전
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
  const result = new Set();
  const counts = new Map();

  const check = (key, target) => {
    if (key === target && key === 0) {
      return counts.get(key) >= 3;
    }

    return counts.has(target) && (key !== target || counts.get(key) > 1);
  };

  for (let i = 0; i < nums.length; i += 1) {
    const now = nums[i];
    counts.set(now, (counts.get(now) ?? 0) + 1);
  }

  counts.forEach((value, key) => {
    counts.forEach((value, target) => {
      const sum = key + target;

      if (check(key, target) && check(key, -sum) && check(target, -sum)) {
        result.add(JSON.stringify([key, target, -sum].sort()));
      }
    });
  });

  return [...result].map(JSON.parse);
};

/**
 * 1시간
 * @note 최적화 이후
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    const result = [];
    
    if (nums.length <= 2) {
        return result;
    }

    nums.sort(sortByAsc);

    let end = nums.length - 1;

    while (end >= 2) {
        let start = 0;
        let middle = end - 1;
        
        const third = nums[end];

        while (start < middle) {
            const first = nums[start];
            const second = nums[middle];

            const sum = first + second + third;

            if (sum > 0) {
                middle -= 1;
            }

            if (sum < 0) {
                start += 1;
            }

            if (sum === 0) {
                result.push([first, second, third]);

                while (second === nums[middle]) {
                    middle -= 1;
                }

                while (first === nums[start]) {
                    start += 1;
                }
            }
        }

        while (third === nums[end]) {
            end -= 1;
        }
    }

    return result;
};

WEEK 6 - 3번 문제


// 3분

class CustomQueue {
    constructor() {
        this.queue = [];
        this.front = 0;
        this.rear = 0;
    }
    enqueue(value) {
        this.queue[this.rear++] = value;
    }
    dequeue() {
        const value = this.queue[this.front];
        delete this.queue[this.front];
        this.front += 1;
        return value;
    }
    peek() {
        return this.queue[this.front];
    }
    get size() {
        return this.rear - this.front;
    }
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
  if (!root) {
      return [];
  }

  const result = [];
  const queue = new CustomQueue();

  queue.enqueue([root, 0]);

  while (queue.size) {
      const [now, depth] = queue.dequeue();

      if (now.left) {
          queue.enqueue([now.left, depth + 1])
      };

      if (now.right) {
          queue.enqueue([now.right, depth + 1])
      };

      result[depth] = [...(result[depth] ?? []), now.val];
  }

  return result;
};

WEEK 6 - 4번 문제


/**
 * // Definition for a Node.
 * function Node(val, neighbors) {
 *    this.val = val === undefined ? 0 : val;
 *    this.neighbors = neighbors === undefined ? [] : neighbors;
 * };
 */

/**
 * @param {Node} node
 * @return {Node}
 */
var cloneGraph = function(node) {
    if (node === null) return node;

    const clone = (node, visited = new Map()) => {
        const now = new Node(node.val);

        visited.set(node.val, now);
        const nowNeighbors = visited.get(node.val).neighbors;
        
        node.neighbors.forEach((neighbor) => {
            const cachedNeighbor = visited.get(neighbor.val);
            
            if (visited.has(neighbor.val)) {
                nowNeighbors.push(cachedNeighbor);
                return;
            }

            const nextNeighbor = clone(neighbor, visited);
            nowNeighbors.push(nextNeighbor);
        })

        return now;
    }

    return clone(node)
};

WEEK 6 - 5번 문제


/**
 * @param {string[]} tokens
 * @return {number}
 */
var evalRPN = function (tokens) {
  const operators = {
    plus: '+',
    subtract: '-',
    multiply: '*',
    divide: '/',
  };

  const operatorSet = new Set(Object.values(operators));

  const passed = [];

  tokens.forEach((token) => {
    if (!operatorSet.has(token)) {
      passed.push(Number(token));
      return;
    }

    const second = passed.pop();
    const first = passed.pop();

    switch (token) {
      case operators.plus: {
        passed.push(first + second);
        return;
      }

      case operators.subtract: {
        passed.push(first - second);
        return;
      }

      case operators.multiply: {
        passed.push(first * second);
        return;
      }

      case operators.divide: {
        const result = first / second;
        passed.push(
          result >= 0 ? Math.floor(first / second) : Math.ceil(first / second)
        );
        return;
      }

      default: {
        return;
      }
    }
  });

  return passed[0];
};

WEEK 6 - 6번 문제


class CustomQueue {
  constructor() {
    this.queue = [];
    this.front = 0;
    this.rear = 0;
  }
  enqueue(value) {
    this.queue[this.rear++] = value;
  }
  dequeue() {
    const value = this.queue[this.front];
    delete this.queue[this.front];
    this.front += 1;
    return value;
  }
  peek() {
    return this.queue[this.front];
  }
  size() {
    return this.rear - this.front;
  }
}

const makeGraph = (numCourses, prerequisites) => {
    const indegrees = Array.from({ length: numCourses }, () => 0);
    const graph = Array.from({ length: numCourses }, () => []);

    prerequisites.forEach(([a, b]) => {
        graph[b].push(a);
        indegrees[a] += 1;
    })

    return { indegrees, graph };
}

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}
 */
var canFinish = function(numCourses, prerequisites) {
    const { indegrees, graph } = makeGraph(numCourses, prerequisites);

    const queue = new CustomQueue();

    indegrees.forEach((indegree, course) => {
        if (!indegree) {
            queue.enqueue(course);
        }
    })

    if (!queue.size()) return false;

    while (queue.size()) {
        const now = queue.dequeue();

        for (let i = 0; i < graph[now].length; i += 1) {
            const nextCourse = graph[now][i];

            indegrees[nextCourse] -= 1;

            if (indegrees[nextCourse] === 0) {
                queue.enqueue(nextCourse);
            }
        }
    }

    return !indegrees.some(Boolean);
};

WEEK 7 - 1번 문제


class Node {
    constructor(value) {
        this.value = value;
        this.isFinished = false;
        this.children = new Map();
        this.cache = new Set();
    }
}

var Trie = function() {
  this.values = new Node(null);

  return this;
};

/** 
 * @param {string} word
 * @return {void}
 */
Trie.prototype.insert = function(word) {
    if (this.values.cache.has(word)) {
        return;
    }

    let nowNode = this.values;

    for (const s of word) {
        const node = new Node(s);

        if (!nowNode.children.has(s)) {
            nowNode.children.set(s, node);
        }
        
        nowNode.cache.add(word);
        nowNode = nowNode.children.get(s);
    }
    
    nowNode.isFinished = true;
};

/** 
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype.search = function(word) {
    if (this.values.cache.has(word)) {
        return true;
    }

    return this.values.cache.has(word);
};

/** 
 * @param {string} prefix
 * @return {boolean}
 */
Trie.prototype.startsWith = function(prefix) {
    let nowNode = this.values;

    for (const s of prefix) {
        if (!nowNode.children.has(s)) {
            return false;
        }

        nowNode = nowNode.children.get(s);
    }

    return true;
};

/** 
 * Your Trie object will be instantiated and called as such:
 * var obj = new Trie()
 * obj.insert(word)
 * var param_2 = obj.search(word)
 * var param_3 = obj.startsWith(prefix)
 */

WEEK 7 - 2번 문제


// 20분
class CustomQueue {
  constructor() {
    this.queue = [];
    this.front = 0;
    this.rear = 0;
  }
  enqueue(value) {
    this.queue[this.rear++] = value;
  }
  dequeue() {
    const value = this.queue[this.front];
    delete this.queue[this.front];
    this.front += 1;
    return value;
  }
  peek() {
    return this.queue[this.front];
  }
  size() {
    return this.rear - this.front;
  }
}


var coinChange = function(coins, amount) {
    if (amount === 0) return 0;
    if (coins.includes(amount)) return 1;

    const DP = new Array(amount + 1).fill(-1);

    const queue = new CustomQueue();

    queue.enqueue([0, 0]) // [숫자, 숫자를 만들기 위해 쓴 동전 카운트]

    while (queue.size()) {
        const [now, count] = queue.dequeue();

        coins.forEach(coin => {
            const next = now + coin; // 수
            const nextCount = count + 1; // next 수를 만들기 위해 하나의 동전을 또 씀

            if (next > DP.length) return; // 넘어가면 의미가 없음 = 리턴

            if (DP[next] === -1) { // 이 숫자가 나오지 않았다면
                DP[next] = nextCount; // 지금 나온 숫자를 만든 카운트가 현재의 정답

                queue.enqueue([next, nextCount]) // 큐에 넣었어요
            }

            if (DP[next] > nextCount) { // 진짜 최적의 답안이 나오면
                queue.enqueue([next, nextCount]); // 최소값을 업데이트
            }
        })
    }

    return DP.at(-1); // 우리가 구하는 숫자를 만들기 위한 동전의 최소값
};


// 최적화
const coinChange = (coins, amount) => {
  const DP = Array(amount + 1).fill(-1);
  
  DP[0] = 0;

  coins.forEach(coin => {
    for (let i = coin; i <= amount; i++) {
      const prev = DP[i - coin]; // 1 2 3 4 5 6 7 8 9 10 -> 2
      
      if (prev === -1) {
          continue;
      }

      if (DP[i] === -1 || DP[i] > prev) {
          DP[i] = prev + 1;
      } // 4 5 -> 11
    }
  })

  return DP[amount];
};

WEEK 7 - 3번 문제


// 7분
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function(nums) {
    const result = new Array(nums.length).fill(0);
    const set = new Set();

    let cachedMultiplyAllValue = 1;

    for (const num of nums) {
        if (num === 0 && set.has(0)) {
            return result;
        }

        set.add(num);

        if (num !== 0) {
            cachedMultiplyAllValue *= num;
        }
    }

    nums.forEach((num, index) => {
        if (set.has(0)) {
            result[index] = num === 0 ? cachedMultiplyAllValue : 0;
            return;
        }

        result[index] = cachedMultiplyAllValue / num;
    })

    return result;
};

WEEK 7 - 4번 문제


/*
 1. 스택을 쌓는데, 계속해서 각 value마다 min값을 캐싱해놓는 거죠
 2. min이라는 것은 마지막 value의 min에 따라서 결정
*/
var MinStack = function() {
    this.value = [];
    this.min = null;
};

/** 
 * @param {number} val
 * @return {void}
 */
MinStack.prototype.push = function(val) {
    this.min =  Math.min(this.min ?? Number.MAX_SAFE_INTEGER, val);

    const nextValue = {
        value: val,
        min: this.min
    }

    this.value.push(nextValue);
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
    this.value.pop();
    this.min = this.value.at(-1)?.min ?? null;
};

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
    return this.value.at(-1).value;
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function() {
    return this.min;
};

WEEK 7 - 5번 문제


/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function(root, range = [-Infinity, Infinity]) {
    if (!root) {
        return true;
    }

    const [from, to] = range;
    const isValid = root.val > from && root.val < to;

    if (!isValid) {
        return false;
    }
 
    const isLeftValid = isValidBST(root.left, [from, root.val]);
    const isRightValid = isValidBST(root.right, [root.val, to]);

    return isLeftValid && isRightValid;
};

WEEK 7 - 6번 문제


class CustomQueue {
  constructor() {
    this.queue = [];
    this.front = 0;
    this.rear = 0;
  }
  enqueue(value) {
    this.queue[this.rear++] = value;
  }
  dequeue() {
    const value = this.queue[this.front];
    delete this.queue[this.front];
    this.front += 1;
    return value;
  }
  get peek() {
    return this.queue[this.front];
  }
  get size() {
    return this.rear - this.front;
  }
}

const MARK = {
    WATER: "0",
    LAND: "1"
};

const bfs = (queue, visible) => {
    const rowLength = visible.length;
    const colLength = visible[0].length;

    const directions = [[0, 1], [0, -1], [-1, 0], [1, 0]];

    while (queue.size) {
        const [x, y] = queue.dequeue();
        
        for (const [dx, dy] of directions) {
            const nx = x + dx;
            const ny = y + dy;

            if (nx < 0 || ny < 0 || nx >= rowLength || ny >= colLength || visible[nx][ny]) {
                continue;
            }

            visible[nx][ny] = true;
            queue.enqueue([nx, ny])
        }
    }
}

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function(grid) {
    const visible = grid.map(row => row.map(col => col === MARK.WATER));

    const queue = new CustomQueue();

    let result = 0;

    grid.forEach((row, rowIndex) => {
        row.forEach((col, colIndex) => {
            if (!visible[rowIndex][colIndex]) {
                result += 1;

                visible[rowIndex][colIndex] = true;
                queue.enqueue([rowIndex, colIndex]);
                
                bfs(queue, visible)
            }
        })
    })

    return result;
};

WEEK 8 - 1번 문제


class CustomQueue {
  constructor() {
    this.queue = [];
    this.front = 0;
    this.rear = 0;
  }
  enqueue(value) {
    this.queue[this.rear++] = value;
  }
  dequeue() {
    const value = this.queue[this.front];
    delete this.queue[this.front];
    this.front += 1;
    return value;
  }
  get peek() {
    return this.queue[this.front];
  }
  get size() {
    return this.rear - this.front;
  }
}

/**
 * @param {number[][]} grid
 * @return {number}
 */

const STATUS = {
    EMPTY: 0,
    FRESH: 1,
    ROTTEN: 2
}

const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];

var orangesRotting = function(grid) {
    let result = 0;
    const queue = new CustomQueue();

    const visible = grid.map((row, rowIndex) => row.map((col, colIndex) => {
        if (col === STATUS.ROTTEN) {
            queue.enqueue([rowIndex, colIndex]);
        }

        return [STATUS.EMPTY, STATUS.ROTTEN].includes(col);
    }));

    while (queue.size) {
        const nextQueue = [];

        const queueSize = queue.size;

        for (let i = 0; i < queueSize; i += 1) {
            const [x, y] = queue.dequeue();

            visible[x][y] = true;

            for (const [dx, dy] of directions) {
                const nx = x + dx;
                const ny = y + dy;

                if (nx >= 0 && ny >= 0 && nx < visible.length && ny < visible[0].length && !visible[nx][ny]) {
                    visible[nx][ny] = true;
                    nextQueue.push([nx, ny])
                }
            }
        }
        
        if (nextQueue.length) {
            result += 1;
        }

        nextQueue.forEach((next) => {
            queue.enqueue(next);
        })
    }

    return visible.every(row => row.every(col => Boolean(col))) ? result : -1;
};

WEEK 8 - 4번 문제


const permutation = (nums, res = []) => {
    if (!nums.length) {
        return res;
    }

    const result = [];

    for (const num of nums) {
        const nextNums = nums.filter(n => n !== num);

        const nextRes = res.length ? res.map(arr => arr.concat([num])) : [[num]];
        
        result.push(...permutation(nextNums, nextRes));
    }

    return result;
}

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
const permute = function(nums) {
    return permutation(nums);
};

WEEK 8 - 5번 문제


/**
 * 1. start를 기준으로 해서 일단 정렬을 시킨다.
 * 2. 그럼 쭉 일자로 될터인데, 결국 이것이 합쳐지려면 뒤의 start가 end보다 작아야 한다.
 * 3. 이 역시 스택에 넣다가, 조건이 충족되지 않으면 스택에 있는 것을 빼내서, 이를 조건에 맞게 다시 넣어준다.
 */

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
const merge = (intervals) => {
  const stack = [];

  [...intervals]
    .sort((a, b) => a[0] - b[0])
    .forEach(([start, end]) => {
        if (!stack.length || stack[stack.length - 1][1] < start) {
            stack.push([start, end]);
            return;
        }

        const [prevStart, prevEnd] = stack.pop();

        stack.push([Math.min(prevStart, start), Math.max(prevEnd, end)]);
    });

  return stack;
};

WEEK 9 - 4번 문제

시간초과

visited에 대한 캐싱을 하지 않았다.


class Q {
  constructor() {
    this.queue = [];
    this.front = 0;
    this.rear = 0;
  }

  enqueue(data) {
    this.queue[this.rear] = data;
    this.rear += 1;
  }
  
  dequeue() {
    const popleft = this.queue[this.front];
    delete this.queue[this.front];
    this.front += 1;
    return popleft;
  }
  
  get size() {
    return this.rear - this.front;
  }
}

class Node {
  constructor(value = '') {
    this.value = value;
    this.isRegistered = false;
    this.children = new Map();
  }
}

class Trie {
  constructor() {
    this.root = new Node();
  }

  insert(string) {
    let currentNode = this.root;

    for (const char of string) {
      if (!currentNode.children.has(char)) {
        currentNode.children.set(char, new Node(currentNode.value + char));
      }

      currentNode = currentNode.children.get(char);
    }

    currentNode.isRegistered = true;
  }

  findNode(string) {
    let currentNode = this.root;

    for (const char of string) {
      if (!currentNode.children.has(char)) {
        return null;
      }

      currentNode = currentNode.children.get(char);
    }

    return currentNode;
  }

  isDict(string) {
    return !!this.findNode(string)?.isRegistered;
  }

  has(string) {
    return !!this.findNode(string);
  }
}


/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = function(s, wordDict) {
    const visited = new Set();
    
    const trie = new Trie();

    wordDict.forEach(word => trie.insert(word));

    const queue = new Q();
    
    queue.enqueue(s);

    while(queue.size) {
        const chars = queue.dequeue();

        if (visited.has(chars)) {
            continue;
        }

        if (!chars) return true;
        
        let s = "";

        for (const char of chars) {
            s += char;

            if (trie.isDict(s)) {
                const next = chars.replace(s, "");

                if (!visited.has(next)) {
                    queue.enqueue(next);
                }
            }
        }
    }

    return false;
};

1차 풀이(해결)

문제는 해결했지만, 시간복잡도 측면에서 매우 비효율적인 것으로 나타났다.


class Q {
  constructor() {
    this.queue = [];
    this.front = 0;
    this.rear = 0;
  }

  enqueue(data) {
    this.queue[this.rear] = data;
    this.rear += 1;
  }
  
  dequeue() {
    const popleft = this.queue[this.front];
    delete this.queue[this.front];
    this.front += 1;
    return popleft;
  }
  
  get size() {
    return this.rear - this.front;
  }
}

class Node {
  constructor(value = '') {
    this.value = value;
    this.isRegistered = false;
    this.children = new Map();
  }
}

class Trie {
  constructor() {
    this.root = new Node();
  }

  // 삽입
  insert(string) {
    let currentNode = this.root;

    for (const char of string) {
      if (!currentNode.children.has(char)) {
        currentNode.children.set(char, new Node(currentNode.value + char));
      }

      currentNode = currentNode.children.get(char);
    }

    currentNode.isRegistered = true;
  }

  // 현재 string에 맞는 총 value를 가진 Node  e -> x -> a -> m -> p -> l -> e
  findNode(string) {
    let currentNode = this.root;

    for (const char of string) {
      if (!currentNode.children.has(char)) {
        return null;
      }

      currentNode = currentNode.children.get(char);
    }

    return currentNode;
  }

  isDict(string) {
    return !!this.findNode(string)?.isRegistered;
  }

  has(string) {
    return !!this.findNode(string);
  }
}


/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = function(s, wordDict) {
    const visited = new Set();
    
    const trie = new Trie();

    wordDict.forEach(word => trie.insert(word));

    const queue = new Q();
    
    queue.enqueue(s);

    while(queue.size) {
        const chars = queue.dequeue();

        if (visited.has(chars)) {
            continue;
        }

        if (!chars) return true;

        visited.add(chars);
        
        let s = "";
        
        // aaaab
        // a, aa, aaa, aaaa

        for (const char of chars) {
            s += char;

            if (trie.isDict(s)) {
                const next = chars.replace(s, "");

                if (!visited.has(next)) {
                    queue.enqueue(next);
                }
            }
        }
    }

    return false;
};

2차 풀이(해결)

원인을 찾아보기 위해 기타 솔루션을 찾아본 결과, visited하는 기준이 달랐던 것을 확인했다.

예컨대, 사실 visited하는 기준은 매 순간 순회할 때마다여야 한다.

설령 만약 특정 문자열 s가 틀리더라도, 이 string은 애초에 틀린 결과를 만들어내는 케이스이니 early return을 해주어야 하는 것이다.

따라서 순회할 때마다 검증할 수 있도록 구조를 바꾸었다.


class Node {
  constructor(value = '') {
    this.value = value;
    this.isRegistered = false;
    this.children = new Map();
  }
}

class Trie {
  constructor() {
    this.root = new Node();
  }

  insert(string) {
    let currentNode = this.root;

    for (const char of string) {
      if (!currentNode.children.has(char)) {
        currentNode.children.set(char, new Node(currentNode.value + char));
      }

      currentNode = currentNode.children.get(char);
    }

    currentNode.isRegistered = true;
  }

  findNode(string) {
    let currentNode = this.root;

    for (const char of string) {
      if (!currentNode.children.has(char)) {
        return null;
      }

      currentNode = currentNode.children.get(char);
    }

    return currentNode;
  }

  isDict(string) {
    return !!this.findNode(string)?.isRegistered;
  }

  has(string) {
    return !!this.findNode(string);
  }
}


/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = function(s, wordDict) {
    const trie = new Trie();

    wordDict.forEach(word => trie.insert(word));

    const visited = new Set();

    const find = (string) => {
        if (string === "") return true;

        if (visited.has(string)) return false;

        visited.add(string);

        let next = "";

        for (const char of string) {
            next += char;

            if (!trie.has(next)) {
                return false;
            }

            if (trie.isDict(next) && find(string.replace(next, ""))) {
                return true;
            }
        }

        return false;
    }

    return find(s);
};

효성

unsolved

dfs에 대한 이해 부족

dfs를 스택으로 만들 줄 몰랐음. 컴퓨팅 파워 퍼포먼스 측면에서 스택이 나음.

최대값에 대한 보장을 하지 못횄음. 그래서 의사결정 단순화를 못함.
모든 합을 다 가져가려고 함.

시간 내 못 풀었음.

민석