알고리즘 STACK, QUEUE

hodu·2023년 4월 13일

개발 공부 알고리즘

STACK 과 QUEUE 는 자바스크립트에서 대표적으로 사용되는 자료 구조이다.
Call Stack과 Task Queue가 바로 그 예시이다.

STACK

이렇게 PUSH와 POP으로 반복되며 나가는 선입 후출 구조이다.

QUEUE

한국 말로 대기줄이라는 뜻으로 선입 선출을 이야기한다.

문제들을 나열할 것이며, 배운 점을 정리하고자 한다.

STACK

올바른 괄호


let check = true;
stack = [];
for (let x of input[0]) {
  if (x === "(") stack.push(x);
  else {
    if (stack.length === 0) check = false;
    stack.pop();
  }
}
log(stack);
if (stack.length > 0) log("NO");
else if (check) log("YES");
else log("NO");

올바른 괄호를 찾는 로직이다.
인상적이었던 것은, (가 먼저 들어올 것을 예상하고,
(가 아니면 pop을 하고, stack 비어있을 경우에는 체크하는 것이 인상적이었다.

그 방법을 통해 비어있으면 올바른 괄호 아닐 경우 체크하는 것이 좋았다.

괄호 문자 제거

let result = [];

1번
for (let i of input[0]) {
   while (i === ")") {
     let j = result.pop();
    if (j === "(") {
     break;
    }
  }
   if (i !== ")") result.push(i);
}
log(result.join(""));

2번
for (let i of input[0]) {
  if (i === ")") {
    while (result.pop() !== "(");
  } else {
    result.push(i);
  }
}
log(result.join(""));

괄호 안에 있는 문자는 제거하고 괄호 밖에 있는 수만 남기는것이다.
좋았던 것은 while을 쓸때 그 자리에서 팝을 하는 것이 좋았다.
그래서 맞을때까지 돌리는 방식으로 자동으로 처리 되는 것이 인상적이었다.

크레인 인형뽑기

let a = [
  [0, 0, 0, 0, 0],
  [0, 0, 1, 0, 3],
  [0, 2, 5, 0, 1],
  [4, 2, 4, 4, 2],
  [3, 5, 1, 3, 1],
];

let b = [1, 5, 3, 5, 1, 2, 1, 4];

let stack = [];
let answer = 0;
b.forEach((v) => {
  for (let i = 0; i < a.length; i++) {
    if (a[i][v - 1] !== 0) {
      let tmp = a[i][v - 1];
      a[i][v - 1] = 0;
      if (stack[stack.length - 1] === tmp) {
        stack.pop();
        answer += 2;
      } else stack.push(tmp);

      break;
    }
  }
});

console.log(answer);

인형뽑기 방식으로 탐색하는 문제이다.
기존의 방식과 다른 것은 많이 없었지만, 2차원 배열에 대한 이해가 중요했고,
넣고나서 0으로 바꾸는 것이나, 넣기 전에 확인하고 넣는 것이 좋았다.

후위식 (postfix) 연산

let a = "352+*9-";
const log = console.log;
log(a);

let stack = [];

for (let i of a) {
  if (!isNaN(i)) stack.push(Number(i));
  else {
    let rt = stack.pop();
    let lt = stack.pop();
    if (i === "+") stack.push(lt + rt);
    else if (i === "-") stack.push(lt - rt);
    else if (i === "*") stack.push(lt * rt);
    else if (i === "/") stack.push(lt / rt);
  }
}

문자열을 체크할 때 split을 하지 않고 이터러블이라는 점을 활용하여서
for of를 쓴게 좋았고, 숫자를 확인할 때 정규식이 먼저 생각났는데 isNaN을 이용하여 확인하는 것이 좋았다.
하드 코딩해야하는 점은 아쉬웠다.

쇠막대기


let a = "()(((()())(())()))(())";

let stack = [];
let answer = 0;
for (let i = 0; i < a.length; i++) {
  if (a[i] === "(") stack.push(a[i]);
  else {
    stack.pop();
    if (a[i - 1] === "(") answer += stack.length;
    else {
      answer += 1;
    }
  }
}
console.log(answer);

제일 어려웠던 문제이다.
문제를 처음 봤을 때 이해가 가지않아서 고생했다.

레이저를 쏘아서 자르는 것인데, () 이렇게 바로 만나면 레이저이고
아닐 경우에는 막대기를 의미하는 것이었다.
그래서 막대가 짤리면 그전가지 있던 ( 갯수를 세어 넣어주었고,

)가 짝을 만나지 않으면 잘리는 것이어서 +1을 해주는 방식으로 풀었다.

식 자체는 어렵지 않은데 접근하고 정리하는 방식이 어려웠다.

QUEUE

공주구하기

let [n, k] = [8, 3];

let queue = Array.from({ length: n }, (n, v) => v + 1); //복습

while (queue.length) {
  for (let i = 1; i < k; i++) queue.push(queue.shift());
  queue.shift();
  if (queue.length === 1) console.log(queue.shift());
}

Array.from 을 활용하는 것이 좋았다.
{}안에 갯수를 선언하고 그 뒤에는 +1을 선언해서 보여주는 것이 좋았다.

이런식의 활용이 가능하다
그리고 그 이후에 queue.push(queue.shift()); 꼬리물기 형식으로 써주는 방식도 좋았다.
빼주는 것은 안넣어주고 갯수 확인해서 1개일때 shift까지 해주면서 while문을 탈출할 수 있었다.

교육과정설계

let a = "CBA";
let b = "CABDGE";

console.log(solution(a, b));

function solution(a, b) {
  let need = a.split("");
  let queue = b.split("");

  for (let i of queue) {
    if (need.includes(i)) {
      if (i !== need.shift()) return "NO"; //복습
    }
  }
  if (need.length > 0) return "NO";
  return "YES";
}