Krong Dev.
알고리즘 Hash DP

leetcode 스터디 1주차 회고 - Hash와 DP로 문제 풀기

Contains Duplicate부터 House Robber까지, DaleStudy leetcode 1주차에 푼 다섯 문제와 코드 리뷰에서 받은 피드백을 정리합니다.

leetcode 스터디 1주차 회고 - Hash와 DP로 문제 풀기

DaleStudy는 LeetCode에서 가장 유명한 문제 모음집인 Blind 75를 함께 풀어나가는 알고리즘 스터디입니다.
매주 정해진 문제를 각자 PR로 제출하고 서로 코드 리뷰를 남기는 방식으로 진행되며, 자세한 진행 방식은 스터디 위키에 정리되어 있습니다.

1주차에는 아래 다섯 문제를 PR로 제출하고 리뷰를 받았습니다.

이 글에서는 1주차 PR에서 풀었던 다섯 문제를 풀기 전에 세웠던 생각 → 실제 구현 → 리뷰어 Zero-1016 님의 피드백 순서로 정리합니다.

문제 한눈에 보기

다섯 문제 모두 시간복잡도 O(n)을 달성했지만, 사용한 자료구조와 패턴은 갈렸습니다.

문제패턴복잡도(시간/공간)
Contains DuplicateHash SetO(n) / O(n)
Two SumHash MapO(n) / O(n)
Top K Frequent ElementsHash Map + Bucket SortO(n) / O(n)
Longest Consecutive SequenceHash SetO(n) / O(n)
House RobberDynamic ProgrammingO(n) / O(n)

Hash 자료구조로 푼 네 문제

Contains Duplicate — Set 크기 비교로 중복 판별 · #217

풀이 전 생각

배열을 Set으로 바꾸면 중복된 값이 자동으로 제거된다는 점에서 출발했습니다.
그렇다면 변환 전후의 길이를 비교하는 것만으로 중복 여부를 판별할 수 있겠다고 생각했습니다.

실제 구현

실제 구현은 이렇게 됐습니다.

javascript
/**
 * @param {number[]} nums
 * @return {boolean}
 */
function containsDuplicate(nums) {
  let set_nums = new Set(nums);

  return set_nums.size !== nums.length;
}

리뷰어 피드백

원래는 if (set_nums.size !== nums.length) return true; else return false; 형태로 조건을 나눠서 반환했습니다.
리뷰어 Zero-1016 님이 조건 자체가 이미 boolean이니 그대로 반환해도 된다는 피드백을 남겨주셨고, 비교식을 바로 반환하는 형태로 다듬었습니다.

리뷰어 Zero-1016 피드백 스크린샷

Set을 다루는 방식과 변수명이 깔끔하다는 총평도 함께 받았는데, 리뷰를 통해 조건문을 얼마나 유연하게 쓰는지가 코드 가독성에 큰 영향을 준다는 걸 다시 느꼈습니다.

Two Sum — 보수 값을 맵에서 먼저 찾기 · #219

풀이 전 생각

문제를 풀기 전에 아래 흐름을 코드에 먼저 주석으로 적어뒀습니다.

map을 사용해서 구하려고 하는 값(인덱스)을 value로 둔다. → {value: index} 역전

map에 {value: index}를 반복하여 저장한다.

in 연산자로 find_num이 map의 key와 일치하는지 비교한다.

target에서 현재 값을 뺀 보수(complement)가 이미 맵에 있는지를 먼저 확인하는 방식으로 접근하겠다는 계획이었습니다.

실제 구현

실제 구현은 이렇게 됐습니다.

javascript
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
function twoSum(nums, target) {
  let map = {};
  let find_num = 0;

  for (let i = 0; i < nums.length; i++) {
    find_num = target - nums[i];

    if (find_num in map) {
      return [map[find_num], i];
    }

    map[nums[i]] = i;
  }
}

순회하면서 현재 값을 저장하기 전에 먼저 보수를 확인하기 때문에, 같은 인덱스를 두 번 쓰는 경우도 자연스럽게 걸러집니다.

리뷰어 피드백

이 문제는 리뷰어 피드백 없이 바로 승인됐습니다.

Top K Frequent Elements — 버킷 정렬로 O(n) 달성 · #237

풀이 전 생각

문제를 풀기 전에 아래와 같이 계획을 세웠습니다.

reduce()를 사용하여 배열에서 각 원소의 빈도수를 구한다.

“버킷 정렬”을 사용한 풀이: 원본 배열의 N+1개의 빈 배열을 생성해서 오름차순으로 원소의 빈도수를 넣는다.

  • 장점: 시간복잡도가 빠름 O(N)
  • 단점: 케이스에 따라 빈 메모리가 많이 소모됨

버킷에서 뒤 원소(빈도수가 많은)부터 하나씩 배열에 넣는다.

즉 정렬 없이 빈도수 자체를 인덱스로 쓰는 버킷을 만들어서 O(n)을 달성하겠다는 계획이었습니다.

실제 구현

실제 구현은 이렇게 됐습니다.

javascript
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
function topKFrequent(nums, k) {
  let result = [];

  let frequency = nums.reduce((acc, count) => {
    acc[count] = (acc[count] || 0) + 1;
    return acc;
  }, {});

  let bucket = Array.from({ length: nums.length + 1 }, () => []);

  for (const [num, count] of Object.entries(frequency)) {
    bucket[count].push(Number(num));
  }

  for (let i = bucket.length - 1; i >= 0; i--) {
    if (bucket[i].length > 0) {
      result.push(...bucket[i]);
    }
  }
  return result.slice(0, k);
}

계획대로 구현하고 나서 빈도가 같은 원소가 여러 개일 때 버킷 안에 배열이 통째로 들어가는 케이스([1, 2] 같은 형태)를 처음엔 놓쳤습니다.
bucket[i] > 0 대신 bucket[i].length > 0으로 비교 조건을 바꿔서 해결했습니다.

리뷰어 피드백

원래는 루프 안에서 result.length === k가 되는 순간 바로
return result.slice(0, k).map(Number)로 끊어내는 방식이었습니다.

리뷰어 Zero-1016 피드백 스크린샷

Zero-1016 님이 Object.entries로 가져온 key가 문자열이라 Number()로 변환하는 이유는 이해했지만 push할 때 이미 형변환을 하고 있어서 문제없어 보인다는 점과, 결과 길이를 확인하는 if문 자체를 지워도 된다는 점을 짚어주셨습니다.
루프 중간에 억지로 끊어내는 것보다 끝까지 순회한 뒤 slice(0, k)로 자르는 편이 더 자연스럽다고 판단해서, 조기 반환 로직과 중복된 .map(Number)를 모두 제거했습니다.

Longest Consecutive Sequence — 시작점만 골라 순회하기 · #240

풀이 전 생각

정렬 없이 O(n)으로 풀려면 각 숫자가 수열의 시작점인지부터 판단해야 한다고 생각했습니다.
num - 1이 Set에 없는 숫자만 시작점으로 보고 그 지점에서부터 연속된 숫자를 세면, 이미 세어본 구간을 중복해서 다시 순회하지 않을 수 있겠다는 계획이었습니다.

실제 구현

실제 구현은 이렇게 됐습니다.

javascript
/**
 * @param {number[]} nums
 * @return {number}
 */
function longestConsecutive(nums) {
  let set_nums = new Set(nums);
  let max_seq = 0;

  if (set_nums.size === 0) return 0;

  for (let num of set_nums) {
    // num-1이 없는 경우 num이 시작 수
    if (!set_nums.has(num - 1)) {
      let curNum = num;
      let seq = 1; // 시작점이 된 순간 seq=1

      while (set_nums.has(curNum + 1)) {
        curNum += 1;
        seq += 1;
      }
      max_seq = Math.max(max_seq, seq);
    }
  }
  return max_seq;
}

리뷰어 피드백

이 문제도 별도의 코드 리뷰 피드백 없이 통과했습니다.

House Robber — DP로 넘어간 다섯 번째 문제 · #264

풀이 전 생각

문제를 풀기 전에 아래와 같이 정리했습니다.

문제에서 중요한 것은 ‘비교를 어디서 어떻게 두나’였다.

[0]번 인덱스에서 시작하거나 [1]번에서 시작하는 두 가지 방식이 있다.

[0]번과 [1]번 각각의 케이스에서 누적된 합을 저장하고 비교한다.

이 값들은 전부 arr 배열의 인덱스에 저장된다.

배열의 원소들이 갖는 의미는 원본 배열 nums의 원소들과 arr 배열의 누적된 값의 합 중 큰 값이다.

이렇게 설계한 경우에 마지막 인덱스 or 마지막 인덱스 -1의 값 중 큰 수인 max number가 반환된다.

인접한 집은 털 수 없다는 제약을 반영해서, 배열 arr에 각 인덱스까지의 최댓값을 누적하는 방식으로 풀겠다는 계획이었습니다.

실제 구현

실제 구현은 이렇게 됐습니다.

javascript
/**
 * @param {number[]} nums
 * @return {number}
 */
function rob(nums) {
  switch (nums.length) {
    case 1:
      return nums[0];
    case 2:
      return Math.max(nums[0], nums[1]);
  }

  let arr = [];
  arr[0] = nums[0];
  arr[1] = nums[1];
  arr[2] = nums[0] + nums[2];

  for (let i = 3; i < nums.length; i++) {
    arr[i] = nums[i] + Math.max(arr[i - 2], arr[i - 3]);
  }

  return Math.max(arr[arr.length - 1], arr[arr.length - 2]);
}

마지막 인덱스와 마지막에서 두 번째 인덱스 중 큰 값이 곧 정답이 되도록 설계했습니다.

리뷰어 피드백

원래 코드에는 switch문에 case 0: return 0; 분기가 남아 있었습니다.
Zero-1016 님이 문제 제약 조건에 이미 nums.length != 0이 명시되어 있어서 이 분기는 불필요해 보인다고 짚어주셨고, 실제로 제약 조건을 다시 확인해보니 맞는 지적이라 바로 제거했습니다.

리뷰어 Zero-1016 피드백 스크린샷

같은 리뷰에서 본인은 Math.max(...arr)로 전체 배열에서 최댓값을 구했는데 마지막 두 값만 비교해도 되는 방식이 좋다는 코멘트도 받았습니다.
같은 문제를 풀어도 최댓값을 확인하는 범위를 배열 전체로 볼지, 마지막 두 칸으로 좁힐지에 따라 접근이 달라질 수 있다는 걸 알게 됐습니다.

마치며

1주차는 대부분 Hash Map과 Hash Set으로 O(n)을 만드는 감을 잡는 주차였고, House Robber에서 처음으로 DP 점화식을 세워봤습니다.
리뷰를 받으면서 두 가지가 확실히 와닿았습니다.

  • 조건문이 이미 boolean을 판단하고 있다면 if/else로 감싸지 말고 그대로 반환하는 게 더 읽기 좋다는 것
  • 문제의 제약 조건을 코드보다 먼저, 더 꼼꼼히 읽어야 불필요한 분기를 만들지 않는다는 것

다음 글에서는 2주차에 푼 Validate Binary Search Tree, 3Sum 같은 문제들을 정리할 예정입니다.

← 목록으로 돌아가기