인프런 알고리즘 5단원 정리

황준·2023년 4월 10일

문제 이름

인프런 05-01번 두 배열 합치기(Two Pointers Algorithm)
인프런 05-02번 공통원소구하기(Two Pointers Algorithm)
인프런 05-03번 연속부분수열1(Two Pointers Algorithm)
인프런 05-04번 연속부분수열2(Two Pointers Algorithm)
인프런 05-05번 최대 매출(Sliding Window)
인프런 05-06번 학급 회장(Hash Map)
인프런 05-07번 아나그램(Hash Map)
인프런 05-08번 모든 아나그램 찾기(Hash & Sliding Window && Two Pointers Algorithm)

두 배열 합치기

                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;

이 문제에서는 while문을 활용한 것이 인상이 깊었다.
남은 잔반 처리를 while문으로 처리하여 자동으로 돌아가도록 한 것이 깔끔했다.

그리고 arr[p1++] 같은 방법으로 arr[p1]을 먼저 찾고 그 이후에 ++해주는 식으로 간편 요약으로 작성한 것이 좋았다.

공통원소 구하기

let first = input[1]
  .split(" ")
  .sort((a, b) => a - b)
  .map(Number);

let second = input[3]
  .split(" ")
  .sort((a, b) => a - b)
  .map(Number);

log(second, first);
let answer = [];
let p1 = (p2 = 0);
while (p1 < first.length && p2 < second.length) {
  if (first[p1] === second[p2]) {
    answer.push(first[p1++]);
    p2++;
  } else if (first[p1] > second[p2]) {
    p2++;
  } else {
    p1++;
  }
}

log(answer)

2개의 배열을 각자 순회하여 체킹하는 문제이다.
위 문제와 비슷하여 수월했다.

또한 한쪽이라도 다 순회하면 더이상 순회할 필요 없어서 심플했다.

연속부분수열1(Two Pointers Algorithm)

let num = input[0].split(" ").map(Number);

num = num[1];

let numArray = input[1].split(" ").map(Number);

let left = 0;
let sum = 0;
let answer = 0;

for (let right = 0; right < numArray.length; right++) {
  sum += numArray[right];
  if (sum === num) {
    answer++;
  }

  while (sum >= num) {
    sum -= numArray[left++];
    if (sum === num) answer++;
  }
}
log(answer);

합쳐서 특정수에 도달하면 체킹하는 시스템이다.
합을 더했을 때 적으면 오른쪽 수가 올라가고,
같으면 정답수가 올라가고 왼쪽 수를 빼주는 방법이다.
상황에 맞추어서 오른쪽과 왼쪽 포인터를 따로 두어서 해결한 것이 어려웠다.

연속부분수열2(Two Pointers Algorithm)


let num = Number(input[0]);

let numArray = input[1].split(" ").map(Number);
let answer = 0;
let sum = 0;

let left = 0;

for (let right = 0; right < numArray.length; right++) {
  sum += numArray[right];
  while (sum > num) {
    sum -= numArray[left++];
  }
  if (sum <= num) {
    answer += right - left + 1;
  }
}
log(answer);

그전 버전에서 업그레이드 되어서 이하까지 포함 하였다.
수열이어서 순서가 존재했고, 같은 숫자임에도 위치가 다르다고 다른 것으로 체킹하는 것이 어려웠다.

또한 오른쪽으로 가면서 하나씩 체킹하는데,
만약에 작으면 right -left +1 하는 방식으로 한칸씩 체크해주면서 넘어가는 것이 인상적이었다. 함축적으로 이 수열에 대해 이해가 없으면 풀기 어려울 것이다.

최대 매출(Sliding Window)

const input = require("fs")
  .readFileSync("20230409/example5.txt")
  .toString()
  .trim()
  .split("\n"); //  .split(/\s+/)
const log = console.log;
log(input);

let num = Number(input[0]);
let numArray = input[1].split(" ").map(Number);

let sum = (answer = 0);

for (let i = 0; i < num; i++) {
  sum += numArray[i];
}
answer = sum;

for (let i = num; i < numArray.length; i++) {
  sum += numArray[i] - numArray[i - num];
  if (sum > answer) answer = sum;
}
log(answer);
// '/dev/stdin'
// [Solved✌🏻]낙준_최대, 최소

// BOJ_10818_N.java

특정 몇일간 연속으로 번 돈이 언제가 가능 많은 것인가? 이다 이 문제의 핵심은
sliding window이다
아래를 보면

두 개념의 차이점을 알 수 있다.

학급 회장(Hash Map)

let countObj = new Map(); // 복습할 것

for (let el of input[0]) {
  if (countObj.has(el)) {
    countObj.set(el, countObj.get(el) + 1); //복습
  } else {
    countObj.set(el, 1);
  }
}

let answer = "";
let max = Number.MIN_SAFE_INTEGER;

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

log(answer);

new Map()이라는 함수로 객체를 만든다
유사 배열 같은 느낌의 객체이다.
has, set, get 을 이용하여 유사 객체를 만들어서 해결한다.

아나그램(Hash Map)

let obj = new Map();

for (let el of input[0]) {
  if (obj.has(el)) {
    obj.set(el, obj.get(el) + 1);
  } else {
    obj.set(el, 1);
  }
}

for (let el of input[1]) {
  if (!obj.has(el) || obj.get(el) === 0) {
    log("NO");
    return;
  } else {
    obj.set(el, obj.get(el) - 1);
  }
}

log("YES");

string도 이터러블이라서 이를 활용하여 풀었다.
먼저 유사 객체를 만들어서 각 알파벳마다 확인하는 방식이다.

모든 아나그램 찾기(Hash & Sliding Window && Two Pointers)

let sWord = input[0];
let tWord = input[1];

let th = new Map();

for (let i of tWord) {
  if (th.has(i)) {
    th.set(i, th.get(i) + 1);
  } else {
    th.set(i, 1);
  }
}
let sh = new Map();

for (let i = 0; i < tWord.length - 1; i++) {
  if (sh.has(sWord[i])) {
    sh.set(sWord[i], sh.get(sWord[i]) + 1);
  } else {
    sh.set(sWord[i], 1);
  }
}

let lt = 0;
let answer = 0;

for (let rt = tWord.length - 1; rt < sWord.length; rt++) {
  if (sh.has(sWord[rt])) {
    sh.set(sWord[rt], sh.get(sWord[rt]) + 1);
  } else {
    sh.set(sWord[rt], 1);
  }
  if (compareHandler(sh, th)) answer++;

  sh.set(sWord[lt], sh.get(sWord[lt]) - 1);
  if (sh.get(sWord[lt]) === 0) sh.delete(sWord[lt]);
  lt++;
}

log(answer);

function compareHandler(sWord, tWord) {
  //지우지 않으면 사이즈에서 다 걸림
  if (sWord.size !== tWord.size) return false;
  for (let [key, val] of tWord) {
    // sword일 경우 지워지지 않는 경우는 x tword로 하는게 지워지지 않았을때보다 더 잘잡아냄
    if (!sWord.has(key)) return false;
    if (sWord.get(key) !== val) return false;
  }

  return true;
}

먼저 체킹해야할 단어를 유사객체로 만들어주고,
그 다음부터는 체킹해야할 단어 -1 만큼을 미리 넣어주어야한다.
왜냐하면 우리는 로직을 시작할때 하나를 넣고 확인할 것이기 때문이다.
이래야 마지막에 끝날 때 체킹하고 끝난다.
처음에는 체킹하고 넣는 것을 고려했으나,
마지막을 고려하니 이 방법이 더 나았다.

답지에서는 compareHandler가 tWord랑 sWord랑 순서가 달랐다.
하지만 tWord를 넣어서 확인하는 것이 더 좋다고 생각한 이유는
만약에 지워지지 않는 키값이 있어도 더 정확하게 측정할 수 있다.