essential
essential

8. Stack

스택을 이해하고 스택을 이용하여 괄호짝 맞추기

Definition of Stack (스택의 정의)

스택은 데이터를 차곡차곡 쌓는 구조로, 마지막에 추가된 데이터가 가장 먼저 제거되는 후입선출(LIFO) 원칙에 따라 동작하는 자료 구조입니다.

🧐 Q. 스택의 “ADT (추상 자료형)” 무엇인가?

스택의 ADT(Abstract Data Type)는 스택이 제공해야 하는 연산과 그 동작 방식을 추상적으로 정의한 것입니다. 즉, 스택 ADT는 스택이 어떻게 동작해야 하는지에 대한 규칙과 연산을 설명하는 것이지, 그 구현방식에 대해 구체적인 내용을 다루지는 않는다.



🧐 Q. 자료형과 추상자료형의 차이는 무엇일까?

  1. 자료형(Data Type) 구체적인 구현 동반
    • 자료형은 구체적인 구현에 대한 정의하는 구체적인 방식이다.
    • 데이터가 메모리에서 어떻게 저장되고, 처리되는지를 정의
    • ex) 정수형(int), 문자열(string), 부동소수점(float) etc
let x = 5; 
/* 

① Javascript에서 정수형 데이터

② 정수형 자료형은 메모리에서 어떻게 정의되어 있으며, 
허용범위(ex. 32비트 정수에서 -2^32 ~ 2^31-1)나 연산방식(덧셈, 뺄셈 등)도 명확하게 정의되어 있다.

③ 구체적인 정의: 정수형 자료형은 실제로 메모리에서 정수값이 어떻게 표현되는지 구체적인 메모리 크기와 범위를 정의하고 있다.

*/


  1. 추상 자료형(Abstract Data Type) 동작하는 것만 정의
    • 추상 자료형은 데이터 동작 방식과 기능을 정의
    • 구체적인 구현 방법과 무관하며, 구현 방식에 관계없이 동일한 동작 보장
    • 스택(Stack), 큐(Queue), 리스트(List), 트리(Tree) etc
class Stack {
    constructor() {
        this.items = [];
    }

    push(item) {
        this.items.push(item);
    }

    pop() {
        if (this.isEmpty()) {
            throw new Error("Stack is empty");
        }
        return this.items.pop();
    }

    peek() {
        if (this.isEmpty()) {
            throw new Error("Stack is empty");
        }
        return this.items[this.items.length - 1];
    }

    isEmpty() {
        return this.items.length === 0;
    }

    size() {
        return this.items.length;
    }
}



🧐 Q. 스택의 세부 동작에 대해 조금 더 자세히 알아보자!

Detailed operation of the stack

Jay Tak


Problem solving

algorithm test

08. Pairing parentheses

Sunhyup Lee. (2024). To be a successful candidate for the coding test. goldenrabbit. p.146.


① The first way to solve the problem : 스택을 이용한 괄호 짝 검사 방식 

function solution(string) {
  const stack = []; // 빈 배열 stack 선언
  for (const parenthesis of string) { 
    // string의 각 문자를 순회하며 parenthesis 변수에 담는다. 즉, 문자열의 각 문자를 하나씩 처리
    if (parenthesis === '(') { 
      // 현재 문자가 '여는괄호'라면 stack 배열에 해당 괄호 추가
      stack.push(parenthesis);
    } else if (parenthesis === ')') { 
      /* 현재 문자가 '닫는괄호'라면 
      1) 스택이 비어 있는지 확인후 비어있을 경우, 괄호가 짝을 이루지 못하므로 false를 반환
      2) 스택이 비어 있는지 확인후 비어있지 않을 경우, 여는 괄호와 짝을 맞춰 스택에서 여는 괄호를 pop
      */ 
      if (stack.length === 0) {
        return false;
      } stack.pop(); 
      // 닫힌 괄호는 바로 pop
    }
  }
  return stack.length === 0;
  // 루프가 끝나면 스택에 남아있는 괄호 여부를 판단해서 true, false 값 반환
}


그외에도 다음과 같은 방식으로도 해결 가능하다

② The second way to solve the problem : 재귀 함수를 이용한 방식 

function isBalanced(string, index = 0, count = 0) {
  // string: 괄호가 포함된 문자열
  // index: 현재 처리하고 있는 문자열의 인덱스. 기본값은 0으로 설정되어 처음부터 시작
  // count: '여는 괄호'의 개수를 추적하기 위한 변수. 기본값은 0으로 설정됩니다.
  if (index === string.length) {
    return count === 0;
  }

  // 여는 괄호일 경우 count 증가
  if (string[index] === '(') {
    return isBalanced(string, index + 1, count + 1);
  }

  // 닫는 괄호일 경우 count 감소
  if (string[index] === ')') {
  // 닫는 괄호가 여는 괄호보다 많으면 false 반환
    if (count === 0) {
	// '여는 괄호' 있는지 확인후 없으면 false 반환
      return false;
    }
    return isBalanced(string, index + 1, count - 1);
  }

  // 다른 문자일 경우 그냥 다음 문자로 넘어감
  return isBalanced(string, index + 1, count);
}

	// 함수 사용 예시
console.log(isBalanced("()()"));  // true
console.log(isBalanced("(())"));  // true
console.log(isBalanced("(()"))    // false


③ The third way to solve the problem : 정규식을 이용한 방식 

function solution(string) {
  // 정규식으로 () 쌍을 반복적으로 제거
  while (string.includes('()')) {
  // ()쌍을 ''(빈문자열)로 대체
    string = string.replace(/\(\)/g, '');
  }
  // 남아 있는 문자열이 있으면 false, 없으면 true
  return string.length === 0;
}

// 함수 사용 예시
console.log(solution("()()"));  // true
console.log(solution("(())"));  // true
console.log(solution("(()"))    // false



Development
Algorithm