자료구조 (스택, 큐)

1. 올바른 괄호

괄호가 입력되면 올바른 괄호이면 “YES", 올바르지 않으면 ”NO"를 출력하는 프로그램.
(())() 이것은 괄호의 쌍이 올바르게 위치하는 거지만, (()()))은 올바른 괄호가 아니다.

스택을 활용한 문제.

👉 스택 : 들어가는 입구와 나가는 출구가 동일한 구조에 활용한다. (가장 나중에 들어간 것이 가장 먼저 나오는 로직 LIFO Last In First Out) push 와 pop을 활용한다.

  //나의 풀이
  function solution(s) {
    let answer = "YES";
    let sH = new Map();
    for (let x of s) {
      sH.has(x) ? sH.set(x, sH.get(x) + 1) : sH.set(x, 1);
    }
    if (sH.get("(") !== sH.get(")")) return "NO";
    return answer;
  }

  선생님 풀이 (스택을 활용하여)
  function solution(s) {
    let answer = "YES";
    let stack = [];
    for (let x of s) {
      if (x === "(") stack.push(x);
      else {
        //')'가 더 많은 상황
        if (stack.length === 0) return "NO";
        stack.pop();
      }
    }
    // '('' 가 더 많은 상황
    if (stack.length > 0) return "NO";
    return answer;
  }

  let a = "(()(()))(()";
  console.log(solution(a)); //"NO"

2. 괄호문자제거 (스택)

입력된 문자열에서 소괄호 ( ) 사이에 존재하는 모든 문자를 제거하고 남은 문자만 출력하는 프로그램을 작성하기.

  function solution(s) {
    let answer;
    let stack = [];
    for (let x of s) {
      if (x === ")") {
        while (stack.pop() !== "(");
      } else stack.push(x);
    }
    answer = stack.join("");

    return answer;
  }

  let str = "(A(BC)D)EF(G(H)(IJ)K)LM(N)";
  console.log(solution(str)); //EFLM

3. 크레인 인형뽑기(카카오 기출)

N x N 크기의 정사각 격자 안에 0~5까지의 다른 종류의 인형들이 있다.
인형을 뽑아 바구니에 아래에서 위로 하나씩 차곡차곡 쌓는다. 만약 바구니의 맨 위에 있는 인형과 뽑은 인형의 종류가 같을 시 두 인형은 사라진다.

게임 화면의 격자의 상태가 담긴 2차원 배열 board와 인형을 집기 위해 크레인을 작동시킨 위 치가 담긴 배열 moves가 매개변수로 주어질 때, 크레인을 모두 작동시킨 후 터트려져 사라진 인형의 개수를 return 하도록 solution 함수를 완성하라.

  function solution(board, moves) {
    let answer = 0;
    let stack = [];
    moves.forEach((pos) => {
      for (let i = 0; i < board.length; i++) {
        if (board[i][pos - 1] !== 0) {
          let tmp = board[i][pos - 1]; // 꺼내기
          board[i][pos - 1] = 0; // 꺼낸 부분 빈공간 만들기
          if (tmp === stack[stack.length - 1]) {
            stack.pop();
            answer += 2;
          } else stack.push(tmp);
          break; // break를 안해주면 한 줄에 있는 모든 인형을 다 꺼내버림, 하나만 꺼낸 뒤 break 걸어주고 다음 postion으로 옮기기
        }
      }
    });

    return answer;
  }

  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];
  console.log(solution(a, b)); //4

4. 후위식 연산(postfix)

후위연산식이 주어지면 연산한 결과를 출력하는 프로그램을 작성하기
만약 3(5+2)-9 을 후위연산식으로 표현하면 352+9- 로 표현되며 그 결과는 12이다.

  function solution(s) {
    let answer;
    let stack = [];

    for (let x of s) {
      if (!isNaN(x)) stack.push(Number(x));
      // 숫자화 시켜서 넣어줄 것!
      else {
        let rt = stack.pop(); // 먼저 나오는 것
        let lt = stack.pop();
        if (x === "+") stack.push(lt + rt);
        else if (x === "-") stack.push(lt - rt);
        else if (x === "*") stack.push(lt * rt);
        else if (x === "/") stack.push(lt / rt);
      }
    }
    answer = stack[0];
    return answer;
  }
  let str = "352+*9-";
  console.log(solution(str)); //12

5. 쇠막대기 (스택)

1 . 레이저는 여는 괄호와 닫는 괄호의 인접한 쌍 ‘( ) ’ 으로 표현된다. 또한, 모든 ‘( ) ’는 반 드시 레이저를 표현한다.
2. 쇠막대기의 왼쪽 끝은 여는 괄호 ‘ ( ’ 로, 오른쪽 끝은 닫힌 괄호 ‘) ’ 로 표현된다.

쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 주어졌을 때, 잘려진 쇠막대기 조각의 총 개수를 구하는 프로그램을 작성하기.

⭐️ 괄호문제는 대부분 스택문제라고 보면 된다.

  function solution(s) {
    let answer = 0;
    let stack = [];
    for (let i = 0; i < s.length; i++) {
      if (s[i] === "(") stack.push(s[i]);
      else {
        stack.pop();
        // 레이저인 경우
        if (s[i - 1] === "(") answer += stack.length;
        else {
          // 막대기가 끝나는 경우
          answer += 1;
        }
      }
    }
    return answer;
  }

  let a = "()(((()())(())()))(())";
  console.log(solution(a)); //17

⭐️ 막대기를 계속 넣다가 레이저가 나오면 레이저 빼주고 answer에 막대기 갯수만큼 더해주고 막대기가 끝나면 answer에 하나 더해주는 로직

6. 공주 구하기 (큐)

1번 왕자부터 N 번 왕자까지 순서대로 시계 방향으로 돌아가며 동그랗게 앉게 한다. 그리고 1번 왕자부터 시계방향으로 돌아가며 1부터 시작하여 번호를 외치게 한다. 한 왕자가 K(특정숫자)를 외치면 그 왕자는 공주를 구하러 가는데서 제외되고 원 밖으로 나오게 된다. 그리고 다음 왕자부터 다시 1부터 시작하여 번호를 외친다.
마지막에 남은 왕자의 번호를 구하는 프로그램 만들기.

👉 큐 : 먼저 들어간게 먼저 나온다. 들어가는 입구와 나오는 출구가 다르다. 배열을 사용한다. First In First Out(FIFO)

  function solution(n, k) {
    let answer = 0;
    let queue = Array.from({ length: n }, (v, i) => i + 1);
    while (queue.length) {
      for (let i = 1; i < k; i++) queue.push(queue.shift());
      queue.shift();
      if (queue.length === 1) answer = queue.shift();
    }

    return answer;
  }

  console.log(solution(8, 3)); //7

7. 교육과정 설계

필수과목순서가 주어지면 N개의 수업설계가 잘된 것이면 “YES", 잘못된 것이면 ”NO“를 출력하는 프로그램을 작성하기.
필수과목의 순서와 수업설계에 들어있는 필수과목의 순서가 일치해야한다.

  function solution(need, plan) {
    let answer = "YES";
    let queue = need.split("");
    for (let x of plan) {
      if (queue.includes(x)) {
        if (queue.shift() !== x) return "NO";
      }
    }
    if (queue.length > 0) return "NO";
    return answer;
  }

  let a = "CBA";
  let b = "CBDAGE";
  console.log(solution(a, b)); //YES