자료구조 | 자바스크립트 스택(stack)

스택 (stack)

Last In Firtst Out 먼저 들어간 자료가 나중에 나오는 후입선출 자료구조

자바스크립트에서 stack은 배열에서 데이터를 입력하는 push() 와 데이터를 제거하는 pop() 의 사용으로 구현할 수 있다. 

 

스택의 시간복잡도

삽입	O(1)
삭제	O(1)
탐색	O(n)

탐색을 할 때 n개 요소를 돌아야하기 때문에 시간복잡도는 O(n)이다. n번째 요소에 접근할 때 pop()을 n번 수행하면 n번째 요소에 접근할 수 있다. pop()의 시간복잡도는 O(1) 이므로 n번째 요소에 접근하는 시간복잡도는 O(n)이다.

 

 

---

예시 문제 1

괄호의 짝이 맞으면 "YES"를 리턴하고, 맞지 않으면 "NO"를 리턴해라

 

const solution = (str) => {
  // 배열을 for문으로 돌면서 (이면 push )이면 pop해서 하나도 안남아있으면 yes 리턴, 하나라도 남아있으면 no 리턴
  let answer = "YES";
  let newArr = [];

  for (let x of str) {
    if (x === '(') newArr.push(x);
    else {
      if (newArr.length === 0) {
        return "No";
      }
      newArr.pop(x);
    }
  }

  if (newArr.length === 0) {
    return answer;
  } else {
    return "NO";
  }
}

const str = "()()"
console.log(solution(str));

 

예시 문제 2

쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다. 쇠막대기를 다른 쇠막대기 위헤 놓는 경우 완전히 포함되도록 놓고, 끝점은 겹치지 않는다.

 

레이저는 괄호의 쌍으로 표현된다 =>  '( )'

쇠막대기의 왼쪽 끝은 여는 괄호 '( ' 이고 오른쪽 끝은 닫힌 괄호 ')'로 표현된다.

 

쇠막대기는 레이저에 의해 몇 개의 조각으로 잘려진다. 

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

 

입력예제

()(((()())(())()))(())

출력예제

17

 

const solution = (str) => {
  let answer = 0;
  let stack = [];

  // 여는 괄호를 만나면 막대기의 시작점 또는 레이저의 시작점이다. -> stack에 푸시
  // 닫는 괄호를 만나면 막대기의 닫는점인지 레이저의 닫는점인지 확인해야한다 -> 바로 앞을 살펴본다

  for (let i = 0; i < str.length; i++) {
    if (str[i] === '(') { // str[i]가 여는 괄호일 경우
      stack.push(str[i]);
    } else { // str[i]가 닫는 괄호일 경우
      stack.pop();
      if (str[i - 1] === '(') { // 레이저인 경우
        // 막대기가 몇 개가 잘리는 지 answer에 카운팅 -> stack의 length 누적
        answer += stack.length;
      } else { // 막대기의 끝인 경우
        // 닫는 괄호를 만나면 무조건 하나는 pop해야한다.
        answer++;
      }
    }
  }
  return answer;
}

const str = "()(((()())(())()))(())";
console.log(solution(str));