✍️문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.

전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

// #시도1. Brute false 문자열 비교, 시간초과
function is_jupdo(target, diff) {
  const target_len = target.length;

  for (let i = 0; i < target_len; i++) {
    if (target[i] !== diff[i]) {
      return false;
    }
  }
  return true;
}

// #시도2. Brute False 숫자 비교, 시간초과
function is_jupdo2(target, diff, power_10) {
  const target_len = target.length;
  const diff_len = diff.length;

  if (Math.floor(diff / power_10[diff_len - target_len]) - target === 0) {
    return true;
  }
  return false;
}
function solution(phone_book) {
  const len = phone_book.length;
  const power_10 = [1];

  // 10의 거듭제곱 값 넣기
  for (let i = 1; i <= 20; i++) {
    power_10[i] = power_10[i - 1] * 10;
  }

  phone_book.sort((a, b) => a.length - b.length);

  for (let i = 0; i < len - 1; i++) {
    const target = phone_book[i];
    for (let j = i + 1; j < len; j++) {
      const diff = phone_book[j];
      // Compare
      if (is_jupdo2(target, diff, power_10)) {
        return false;
      }
    }
  }
  return true;
}

2️⃣Hash Table

1. phone_number 값을 객체 (Hash Table)에 저장한다. (아래 그림 참고)

2. 각 phone_number를 순회하며, 생성가능한 모든 접두어가 객체(Hash Table)에 존재하는지 확인한다.

// 시도3: Hash Table만들기
function solution(phone_book) {
  const table = {};
  for (const phone of phone_book) {
    table[phone] = true;
  }

  for (const phone of phone_book) {
    const len = phone.length;
    for (let i = 1; i < len; i++) {
      const substr = phone.substring(0, i);
      if (table[substr] === true) {
        return false;
      }
    }
  }

  return true;
}

분석

1️⃣Brute False

• solution 함수에서는 전화번호를 길이 순으로 정렬한 후, 각 번호와 그 다음 번호들 간의 비교를 반복한다.
• 여기서 이중 반복문을 사용하므로, 시간 복잡도는 최악의 경우 O(n^2)이다.
• 또한, is_jupdo 호출은 두 문자열의 길이에 비례하여 O(m) 시간이 소요되며, 이는 두 문자열 길이의 최대값에 의해 결정된다.
• 따라서 전체 시간 복잡도는 `O(n^2×m)`로, 전화번호의 수가 많거나 각 번호의 길이가 길면 성능이 최악이다.

2️⃣Hash Table

• 해시 테이블에 각 전화번호를 저장한 후, 각 전화번호의 접두사가 테이블에 있는지 확인한다. (O(n))
• 각 phone_number의 길이-1 만큼 hash table에 접두어가 있는지 확인한다. (O(m))
• 따라서, 이 방법의 시간 복잡도는 `O(n×m)`로, n은 전화번호 개수이고, m은 각 전화번호의 길이이다.

기존에 Stack을 다룰 때, 값들을 Stack에 넣어서 사용하는 간단한 문제만 풀어보다가 index를 스택에 저장하여 사용하는 방식의 문제가 있어서 기록합니다.

✏️ 문제 설명

temperatures 배열의 각 원소에 대해 자신보다 큰 값이 나오는 Index 차이를 알아내어, 해당 값을 output 배열에 넣어 반환.

Approach 1. O(n^2) : Brute False

변수선언 `output[]`: 정답을 저장할 배열

1. `stack[]` : 순회한 값들을 저장할 배열
2. `temperatures[]` 의 뒤에서부터 순회한다.
   • 각 temperature에 대해 스택의 앞에서 부터 순회하며, temperature보다 큰 값을 구할 때 까지 count 한다.
   • 큰 값이 나오면, 해당 값을 `ouput[]`의 맨 앞에 추가한다.

var dailyTemperatures1 = function (temperatures) {
  const output = [];
  let stack = [];
  while (temperatures.length > 0) {
    const target = temperatures.pop();
    let cnt = 0;
    let flag = false;
    for (const num of stack) {
      if (num <= target) cnt++;
      else {
        cnt++;
        flag = true;
        break;
      }
    }
    stack.unshift(target);
    if (flag) {
      output.unshift(cnt);
    } else {
      output.unshift(0);
    }
  }
  return output;
};

Time Out Error!

n ≤ 10^5 이므로, 10^4 * 10^4 = 1초 원칙에 의거 시간이 부족함.

Approach 2. O(n) : Stack (Monotonic Decreasing)

1. 변수선언
   `idx_stack[]` : output이 정해지지 않은 temperatures의 index를 저장한 배열
   `ouput[]` : 결과값을 저장할 배열
2. `temperatures []`순회
   각 temperature에 대해, `idx_stack[]` 의 뒤에서 부터, 자신보다 값이 작은게 오면, pop() 하여 output에 index 차이를 저장

var dailyTemperatures = function (temperatures) {
  const len = temperatures.length;

  const idx_stack = [];
  const output = new Array(len).fill(0);

  for (let i = 0; i < temperatures.length; i++) {
    const target = temperatures[i];
    while (
      idx_stack.length > 0 &&
      target > temperatures[idx_stack[idx_stack.length - 1]]
    ) {
      const idx = idx_stack.pop();
      output[idx] = i - idx;
    }
    idx_stack.push(i);
  }
  return output;
};

공유하고 싶었던 내용

1. ⭐ Stack을 다룰 때, index만을 다룰 수 있다는 유연함 ⭐
2. Monotonic 배열에서 while 문을 통한 배열 checking