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

1. 두 배열 합치기

오름차순으로 정렬이 된 두 배열이 주어지면 두 배열을 오름차순으로 합쳐 출력하는 프로그램 작성하기.

  function solution(arr1, arr2) {
    // 나의 풀이
    // let answer = [];
    // answer = [...arr1, ...arr2].sort((a, b) => a - b);
    // 선생님 풀이

    let answer = [];
    let n = arr1.length;
    let m = arr2.length;
    let p1 = (p2 = 0);
    while (p1 < n && p2 < m) {
      if (arr1[p1] <= arr2[p2]) answer.push(arr1[p1++]);
      else answer.push(arr2[p2++]);
    }
    while (p1 < n) answer.push(arr1[p1++]);
    while (p2 < m) answer.push(arr2[p2++]);
    return answer;
  }
   let a=[1, 3, 5];
   let b=[2, 3, 6, 7, 9];
   console.log(solution(a, b));  //[1, 2, 3, 3, 5, 6, 7, 9]

👉 알아두어야 할 점 : sort는 되도록 쓰지 않는 게 좋다. nlogn함수라 시간복잡도가 커지므로.
⭐️ 핵심 포인트 : 두 포인터 변수를 활용하자. (two pointers algorithm)

2. 공통원소 구하기

two pointers 로 풀 수 있는 문제
A, B 두 개의 집합이 주어지면 두 집합의 공통 원소를 추출하여 오름차순으로 출력하는 프로그램을 작성하기

  function solution(arr1, arr2) {
    let answer = [];
    arr1.sort((a, b) => a - b);
    arr2.sort((a, b) => a - b);
    let p1 = (p2 = 0);
    while (p1 < arr1.length && p2 < arr2.length) {
      if (arr1[p1] === arr2[p2]) {
        answer.push(arr1[p1++]);
        p2++;
      } else if (arr1[p1] > arr2[p2]) p2++;
      else p1++;
    }
    return answer;
  }
  let a = [1, 3, 9, 5, 2];
  let b = [3, 2, 5, 7, 8];
  console.log(solution(a, b)); //2 3 5

3. 연속부분수열

N개의 수로 이루어진 수열에서 연속부분수열의 합이 특정숫자 M이 되는 경우가 몇 번 있는지 구하는 프로그램을 작성하기.

⭐️ 코드 이해 매우 중요 !
⭐️ 2 points algorithm : O(n)

  function solution(m, arr) {
    let answer = 0;
    let sum = 0;
    let lt = 0; // lt = left, rt = right

    for (let rt = 0; rt < arr.length; rt++) {
      sum += arr[rt];
      if (sum === m) answer++;
      while (sum > m) {
        sum -= arr[lt++];
        if (sum === m) answer++;
      }
    }
    return answer;
  }

  let a = [1, 2, 1, 3, 1, 1, 1, 2];
  console.log(solution(6, a)); //3

4. 연속 부분수열 2

N개의 수로 이루어진 수열에서 연속부분수열의 합이 특정숫자 M이하가 되는 경우가 몇 번 있는지 구하는 프로그램을 작성하기

    function solution(m, arr) {
      let answer = 0,
        sum = 0,
        lt = 0;
      for (let rt = 0; rt < arr.length; rt++) {
        sum += arr[rt];
        while (sum > m) {
          sum -= arr[lt++];
        }
        answer += rt - lt + 1;
      }

      return answer;
    }
    let a = [1, 3, 1, 2, 3];
    console.log(solution(5, a)); //10
    

5. 최대 매출

n개의 수열에서 연속 k개 부분수열의 합들을 구하고 그 중 최댓값을 구하는 프로그램 만들기.
만약 K=3이면
12 15 11 20 25 10 20 19 13 15에서 3개 부분수열의 최댓값은 11+20+25=56이다.

⭐️ sliding window algorithm : i를 쭉 밀고 나가면서 앞의 i-k를 계속 빼주는 방식

  function solution(k, arr) {
    let answer,
      sum = 0;
    for (let i = 0; i < k; i++) sum += arr[i];
    answer = sum;
    for (let i = k; i < arr.length; i++) {
      sum += arr[i] - arr[i - k];
      answer = Math.max(answer, sum);
    }

    return answer;
  }

  let a = [12, 15, 11, 20, 25, 10, 20, 19, 13, 15];
  console.log(solution(3, a)); //56

6. 학급회장 (해쉬)

A, B, C, D, E 중 가장 많이 나온 알파벳 출력하기

⭐️ Map 을 활용한다. (해쉬로 사용되는 객체가 생성된다.)
⭐️ Map에서의 get, set 알아두기

  function solution(str) {
    let answer;
    let sH = new Map(); // sH = string Hash
    for (let x of str) {
      if (sH.has(x)) sH.set(x, sH.get(x) + 1);
      else sH.set(x, 1);
    }
    let max = Number.MIN_SAFE_INTEGER;
    for (let [key, val] of sH) {
      if (val > max) {
        max = val;
        answer = key;
      }
    }

    return answer;
  }

  let str = "BACBACCACCBDEDE";
  console.log(solution(str)); //C

7. 아나그램 (해쉬)

길이가 같은 두 개의 단어가 주어지면 두 단어가 아나그램인지 판별하는 프로그램을 작성하기. 아나그램 판별시 대소문자가 구분된다.

  //객체를 활용한 풀이
  function solution(str1, str2) {
    let answer = "YES";
    let objectStr1 = {};
    let objectStr2 = {};

    for (let x of str1) {
      objectStr1[x] ? (objectStr1[x] += 1) : (objectStr1[x] = 1);
    }

    for (let x of str2) {
      objectStr2[x] ? (objectStr2[x] += 1) : (objectStr2[x] = 1);
    }
    console.log(objectStr1, objectStr2);
    for (let key in objectStr1) {
      if (!objectStr2[key]) return "NO";

      if (objectStr1[key] !== objectStr2[key]) return "NO";
    }

    return answer;
  }

  //선생님 풀이
  function solution(str1, str2) {
    let answer = "YES";
    let sH = new Map();
    if (str1.length !== str2.length) return "NO";
    for (let x of str1) sH.has(x) ? sH.set(x, sH.get(x) + 1) : sH.set(x, 1);
    for (let x of str2) {
      if (!sH.has(x) || sH.get(x) === 0) return "NO";
      sH.set(x, sH.get(x) - 1);
    }
    return answer;
  }
  let a = "AbaAeCe";
  let b = "baeeACA";
  console.log(solution(a, b)); // "YES"

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

S문자열에서 T문자열과 아나그램이 되는 S의 부분문자열의 개수를 구하는 프로그램을 작성하기. 아나그램 판별시 대소문자가 구분된다. 부분문자열은 연속된 문자열이어야 한다.

  function compareMaps(map1, map2) {
    //참고 ) map.size : map 내의 key의 종류
    if (map1.size !== map2.size) return false;

    for (let [key, val] of map1) {
      if (!map2.has(key) || map2.get(key) !== val) return false;
    }
    return true;
  }
  function solution(s, t) {
    let answer = 0;
    let tH = new Map();
    let sH = new Map();
    for (let x of t) tH.has(x) ? tH.set(x, tH.get(x) + 1) : tH.set(x, 1);
    let len = t.length - 1;
    for (let i = 0; i < len; i++) {
      sH.has(s[i]) ? sH.set(s[i], tH.get(s[i]) + 1) : sH.set(s[i], 1);
    }
    let lt = 0;
    for (let rt = len; rt < s.length; rt++) {
      sH.has(s[rt]) ? sH.set(s[rt], tH.get(s[rt]) + 1) : sH.set(s[rt], 1); // set 에 rt 하나 추가
      if (compareMaps(sH, tH)) answer++; // 두 map 의 비교
      sH.set(s[lt], sH.get(s[lt]) - 1); // 비교 후 lt 하나 제거해주기
      if (sH.get(s[lt]) === 0) sH.delete(s[lt]); // 만약 lt 값이 0이라면 key 값 자체를 제거해주기
      lt++; // lt값 증가!
    }

    return answer;
  }

  let a = "bacaAacba";
  let b = "abc";
  console.log(solution(a, b)); //3
  

⭐️ "빼고 -> 추가 -> 비교" 의 논리