알고리즘

1. Sliding Window 🪟

이전 투포인터 알고리즘은 일렬로 나열된 데이터에 두개에 포인터로 비교해야할 때 필요한 알고리즘이었다.
투포인터 알고리즘은 1차원 배열에서 각각 다른 요소를 조작하여 원하는 값을 얻는 방법으로 주로 연속부분수열에 사용되어 아래와 같은 방식으로 움직여야한다.

하지만 슬라이딩 윈도우는 1차원 배열에서 정해진 크기만큼 연속적으로 계산을 하고 움직이며 창문을 미는 것처럼 움직인다.

⭐️ 포인트는 연속적, 일정적

포인트는 연속적으로 일정하게 계산을 해나가는데 중첩되는 교집합은 공유하고 양끝의 데이터는 차이가 난다.
그러므로 보통 특정 기간동안의 값이나 위치를 반환해야할 때 사용해야할 것으로 보인다.

🧑‍💻 사용법(문제)

최대매출
현수의 아빠는 제과점을 운영합니다. 현수 아빠는 현수에게 N일 동안의 매출기록을 주고
연속 된 K일 동안의 최대 매출액이 얼마인지 구하라고 했습니다.
만약 N=10이고 10일 간의 매출기록이 아래와 같습니다. 이때 K=3이면
12 15 11 20 25 10 20 19 13 15
연속된 3일간의 최대 매출액은 11+20+25=56만원입니다. 여러분이 현수를 도와주세요.

▣ 입력설명
첫 줄에 N(5<=N<=100,000)과 K(2<=K<=N)가 주어집니다.
두 번째 줄에 N개의 숫자열이 주어집니다. 각 숫자는 500이하의 음이 아닌 정수입니다.
▣ 출력설명
첫 줄에 최대 매출액을 출력합니다.

function solution(k, arr) {
  let answer, // 최대 매출액
    sum = 0; // 합계

  for (let i = 0; i < k; i++) sum += arr[i]; //  초기 k 날만큼의 합계 
  answer = sum; // 초기 최대매출로 할당
  for (let i = k; i < arr.length; i++) {
    const dif = arr[i] - arr[i - k]; //** 추가되는 날과 지나간 날의 매출을 빼 차이를 계산 */
    sum += dif;
    answer = Math.max(answer, sum); // 가장 큰 매출액으로 재할당
  }

  return answer;
}

다른 풀이2

투포인터를 사용한 풀이

function solution2(k, arr) {
  let answer = (rt = sum = 0); // 포인터(rt) 추가 

  const n = arr.length;
  for (let lt = 0; lt < n - k + 1; lt++) { // 포인터(lt) 추가
    while (rt - lt < k) { // 두 개의 포인터의 차이가 k 날이 넘지 않도록 while
      sum += arr[rt++]; // 하나의 포인터가 늘어나며 순차적으로 이동하며 합계를 더함
    }

    answer = Math.max(answer, sum); // 더한 값에서 최대 매출 값을 재할당
    sum -= arr[lt]; // 순차적으로 이동하며 합계에서 지나갈 데이터를 뻄
  }

  return answer;
}

두 개의 포인터가 같은 방향으로 움직이며 두 포인터의 차이가 k를 넘기지 않도록 하여 일정한 크기를 제한했고 다음 데이터로 넘어가기 전에 지나온 데이터를 빼주는 방식으로 풀이

다른 풀이3

배열의 고차함수를 사용하여 풀이

function solution3(k, arr) {
  let answer,
    sum = 0;

  for (let i = 0; i <= arr.length - k; i++) {
    const newArr = [...arr].slice(i, i + k); // .slice() 를 사용하여 k일 만큼의 각각 매출을 2차원 배열로 
    sum = newArr.reduce((a, b) => a + b); // 각 날마다 매출의 합을 구함
    answer = Math.max(answer, sum); 
  }

  return max;
}

풀이3의 경우
answer의 길이만큼 돌기 때문에 이중 for문
시간복잡도 O(n^2)
풀이1, 풀이2는 for의 i만큼 반복이기 때문에 시간 복잡도 0(n)

2. Hash Map(Map)

해시맵 알고리즘은 key(키): value(값) 쌍을 저장하고, 키를 통해 값을 빠르게 검색, 삽입, 삭제 할 수 있는 데이터 구조다.
key(키): value(값)로 이루어진 데이터. 쉽게 말해 객체다. 객체가 아닌것이 없는 세상.

⭐️ Map() 사용법

let person = new Map();

// 값 할당
person.set("name", "John");
person.set("age", 21);

// 값 가져오기
console.log(person.get("name")); // John
console.log(person.get("age")); // 21

// 키 존재 여부 확인
console.log(person.has("name")); // true
console.log(person.has("gender")); // false

// 값 삭제
person.delete("name");

// 순회
person.forEach((value, key) => {
  console.log(`${key}: ${value}`);
});

//key, value 쌍으로 출력
for (let [key, value] of person) {
  console.log(`${key}: ${value}`);
};

//key만 출력
for (let key of person.keys()) {
  console.log(key);
};

//value만 출력
for (let value of person.values()) {
  console.log(value);
};

// key - value 쌍의 개수
console.log(person.size);

// 맵의 모든 키-값 쌍을 [key, value] 형태의 array로 만들어서 반환 [[key, value], [key, value]...]
console.log(person.entries())

// 초기화
person.clear();

Hash 문제

학급 회장(해쉬) Hash Map
학급 회장을 뽑는데 후보로 기호 A, B, C, D, E 후보가 등록을 했습니다.
투표용지에는 반 학생들이 자기가 선택한 후보의 기호(알파벳)가 쓰여져 있으며 선생님은 그 기호를 발표하고 있습니다.
선생님의 발표가 끝난 후 어떤 기호의 후보가 학급 회장이 되었는지 출력하는 프로그램을 작 성하세요. 반드시 한 명의 학급회장이 선출되도록 투표결과가 나왔다고 가정합니다.

▣ 입력설명
첫 줄에는 반 학생수 N(5<=N<=50)이 주어집니다.
두 번째 줄에 N개의 투표용지에 쓰여져 있던 각 후보의 기호가 선생님이 발표한 순서대로 문자열로 입력됩니다.
▣ 출력설명
학급 회장으로 선택된 기호를 출력합니다.

function solution(n, arr) {
  let answer = "",
    max = Number.MIN_SAFE_INTEGER;
  let map = new Map();

  for (let x of arr) {
    const count = map.get(x); // 객체에 해당 후보가 있는지 확인
    map.set(x, count ? count + 1 : 1); // 해당 후보가 있으면 1표 추가, 없으면 1 저장
    max = Math.max(...map.values()); // 가장 많은 득표수 할당
  }

  for (let [key, value] of map) {
    if (value === max) answer = key;
  }
  return answer;
}

Hash 문제(아나그램)

아나그램
Anagram이란 두 문자열이 알파벳의 나열 순서를 다르지만 그 구성이 일치하면 두 단어는 아나그램이라고 합니다.
예를 들면 AbaAeCe 와 baeeACA 는 알파벳을 나열 순서는 다르지만 그 구성을 살펴보면
A(2), a(1), b(1), C(1), e(2)로 알파벳과 그 개수가 모두 일치합니다.
즉 어느 한 단어를 재 배열하면 상대편 단어가 될 수 있는 것을 아나그램이라 합니다.
길이가 같은 두 개의 단어가 주어지면 두 단어가 아나그램인지 판별하는 프로그램을 작성하세요. 아나그램 판별시 대소문자가 구분됩니다.

▣ 입력설명
첫 줄에 첫 번째 단어가 입력되고, 두 번째 줄에 두 번째 단어가 입력됩니다. 단어의 길이는 100을 넘지 않습니다.
▣ 출력설명
두 단어가 아나그램이면 “YES"를 출력하고, 아니면 ”NO"를 출력합니다.

function solution1(str1, str2) {
  let answer = "NO";
  const newMap = new Map();

  for (let x of str1) {
    const target = newMap.get(x);
    newMap.set(x, target ? target + 1 : 1);
  }

  for (let y of str2) {
    const target = newMap.get(y);
    target && newMap.set(y, target - 1);
  }
  const filter = [...newMap.values()].find((count) => count !== 0); // 다른게 있는 지 확인(find)
  answer = filter ? "NO" : "YES";
  return answer;
}

하지만 위 코드대로하면 반복문과 고차함수까지 너무 많은 로직이 있다.
리펙터링해보자.

function solution2(str1, str2) {
  let answer = "YES";
  const newMap = new Map();

  for (let x of str1) {
    const target = newMap.get(x);
    newMap.set(x, target ? target + 1 : 1);
  }

  for (let y of str2) {
    const target = newMap.get(y);
    if (!target || target === 0) return "NO"; // 같은 문자열이 없는지 & 더이상 같은 문자가 없는지 확인
    target && newMap.set(y, target - 1);
  }
  return answer;
}

이런식으로 풀수있다.

📚 마무리

언제나 어려운 알고리즘 공부~ 포기하지 말고 꾸준히 해보자.