Skip to main content

05. 효율성(투포인터 알고리즘, 슬라이딩윈도우, 해시)

효율성(투포인터 알고리즘, 슬라이딩윈도우, 해시)​

투포인터​

투 포인터 알고리즘 (Two Pointers Algorithm)은 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘

슬라이딩 윈도우​

슬라이딩 윈도우 알고리즘 (Sliding Window Algorithm)은 이름과 같이 윈도우(Window) 일정한 틀을 갖고 끝까지 쭉 순회하는 알고리즘이다.

해시​

해시 테이블 (Hash Table)은 어떤 특정 값을 받으면 그 값을 해시 함수에 통과시켜 나온 인덱스(index)에 저장하는 자료구조이다.

문제 풀이​

Ch.05 - 01. 두 배열 합치기​

function solution(arr1, arr2) {
  const answer = [];
  const arr1Length = arr1.length;
  const arr2Length = arr2.length;

  let arr1Pointer = 0;
  let arr2Pointer = 0;
  while (arr1Pointer < arr1Length && arr2Pointer < arr2Length) {
    const arr1Value = arr1[arr1Pointer];
    const arr2Value = arr2[arr2Pointer];

    if (arr1Value <= arr2Value) {
      answer.push(arr1[arr1Pointer++]);
    } else if (arr2Value < arr1Value) {
      answer.push(arr2[arr2Pointer++]);
    }
  }

  while (arr1Pointer < arr1Length) answer.push(arr1[arr1Pointer++]);
  while (arr2Pointer < arr2Length) answer.push(arr2[arr2Pointer++]);

  return answer;
}

Ch.05 - 02. 공통원소 구하기​

function solution(arr1, arr2) {
  const answer = [];

  const sortedArr1 = [...arr1].sort((a, b) => a - b);
  const sortedArr2 = [...arr2].sort((a, b) => a - b);

  for (let i = 0, j = 0; i < arr1.length && j < arr2.length; ) {
    if (sortedArr1[i] === sortedArr2[j]) {
      answer.push(sortedArr1[i++]);
      j++;
    } else if (sortedArr1[i] < sortedArr2[j]) i++;
    else if (sortedArr1[i] > sortedArr2[j]) j++;
  }
  return answer;
}

Ch.05 - 03. 연속 부분수열 1​

function solution(m, arr) {
  let answer = 0;
  const arrLength = arr.length;

  let startPointer = 0;
  let endPointer = 0;
  let sumNum = 0;
  while (endPointer < arrLength) {
    if (sumNum === m) {
      answer++;
      sumNum -= arr[startPointer++];
      sumNum += arr[++endPointer];
    } else if (m < sumNum) {
      sumNum -= arr[startPointer++];
    } else if (sumNum < m) {
      sumNum += arr[++endPointer];
    }
  }
  return answer;
}

Ch.05 - 04. 연속 부분수열 2​

function solution(m, arr) {
  let answer = 0;
  const arrLength = arr.length;

  next: for (let i = 0; i < arrLength; i++) {
    let remainNum = m;
    for (let j = i; j < arrLength; j++) {
      remainNum -= arr[j];

      if (0 <= remainNum) answer++;
      else continue next;
    }
  }

  return answer;
}

Ch.05 - 05. 최대 매출​

function solution(k, arr) {
  let answer = 0;
  const arrLength = arr.length;

  for (let i = 0; i < k; i++) answer += arr[i];

  let curSales = answer;
  for (let j = k; j < arrLength; j++) {
    curSales = curSales - arr[j - k] + arr[j];

    answer = Math.max(answer, curSales);
  }

  return answer;
}

Ch.05 - 06. 학급 회장(해쉬)​

function solution(arr) {
  let answer = null;
  const cacheMap = new Map();

  for (let candidate of arr) {
    if (cacheMap.has(candidate))
      cacheMap.set(candidate, cacheMap.get(candidate) + 1);
    else cacheMap.set(candidate, 1);
  }

  let maxVote = 0;
  for (let [key, value] of cacheMap) {
    if (maxVote < value) {
      answer = key;
      maxVote = value;
    }
  }

  return answer;
}

Ch.05 - 07. 아나그램(해쉬)​

function solution(str1, str2) {
  const cacheMap = new Map();

  for (const addChar of str1) {
    if (cacheMap.has(addChar)) cacheMap.set(addChar, cacheMap.get(addChar) + 1);
    else cacheMap.set(addChar, 1);
  }

  for (const removeChar of str2) {
    if (!cacheMap.has(removeChar) || cacheMap.get(removeChar) === 0)
      return "NO";
    else cacheMap.set(removeChar, cacheMap.get(removeChar) - 1);
  }

  return "YES";
}

Ch.05 - 08. 모든 아나그램 찾기(해쉬, 투포인터, 슬라이딩 윈도우)​

function solution(strS, strT) {
  let answer = 0;

  // str2를 해쉬 값으로 변경
  const cacheObjStrT = new Map();
  for (const charT of strT) {
    if (cacheObjStrT.has(charT))
      cacheObjStrT.set(charT, cacheObjStrT.get(charT) + 1);
    else cacheObjStrT.set(charT, 1);
  }

  // for문을 돌면서 str2와 같은 길이의 문자열을 해쉬 값으로 변경해서 비교 연산
  const cacheObjStrS = new Map();
  next: for (let j = 0; j < strS.length; j++) {
    const charS = strS[j];
    if (cacheObjStrS.has(charS))
      cacheObjStrS.set(charS, cacheObjStrS.get(charS) + 1);
    else cacheObjStrS.set(charS, 1);

    const removeCharS = strS[j - strT.length];
    if (1 < cacheObjStrS.get(removeCharS))
      cacheObjStrS.set(removeCharS, cacheObjStrS.get(removeCharS) - 1);
    else cacheObjStrS.delete(removeCharS);

    for (const [key] of cacheObjStrT) {
      if (cacheObjStrT.get(key) !== cacheObjStrS.get(key)) continue next;
    }
    answer++;
  }
  return answer;
}