스택(Stack)이란? (+ 알고리즘 문제 풀이 )

1. 스택(Stack)이란?

• 스택은 컴퓨터에서 많이 사용되는 자료구조이다.
  ( 자료구조는 대량의 데이터를 효율적으로 관리할 수 있는 데이터의 구조를 의미한다. )

• 특징
  1) 스택은 LIFO(Last In First Out)후입선출 구조이다.
  2) 가장 최근에 들어온 데이터가 가장 먼저 나간다는 의미이다.
  3) 아래는 스택 구조를 이미지로 설명한 것이다. 마지막에 들어온 데이터가 가장 빨리 빠져나가는 구조임을 확인할 수 있다.

2. 스택 기초 알고리즘 및 풀이

아래 알고리즘 문제를 접했고, 먼저 생각나는데로 구현을 해보았습니다. 그리고 좀 더 정석적인 방법이 있을거라고 생각해서 자료구조에 대해 조사하고 적용해 보았습니다.

https://school.programmers.co.kr/learn/courses/30/lessons/12909
-> 프로그래머스 문제이다.

문제 : 괄호() 가 올바른 쌍이면 true , 올바르지 않으면 false를 반환하는 함수를 만들어라

ex)
(()()) => true
((() => false
()()(()) => true

(1) 처음 문제를 봤을 때 나의 풀이

• 단계별로 나누어서 아래와 같이 풀이를 진행했다.

function solution(data) {
  let answer = [];
  /*
  1. 문자열을 split을 이용해 arr 배열을 만든 후 , filter를 이용해 빈칸" "을 없애자
  2. 빈칸을 제거했기 떄문에 배열의 크기가 홀수이면 짝이 맞지 않으므로 FALSE를 반환시키자
  3. 최소 단위의 괄호부터 소거하여 , 제일 외각의 괄호까지 소거시키는 반복문을 실행
  4. 반복문 완료 후에, 소거된 배열의 길이가 0이면 true , 0 초과면 false를 반환시킨다.
  */

  // 1. 문자열을 split을 이용해 arr 배열을 만든 후 , filter를 이용해 빈칸" "을 없애자
  let arr = data.split("").filter((item) => item !== " ");

  // 2. 빈칸을 제거했기 떄문에 배열의 크기가 홀수이면 짝이 맞지 않으므로 FALSE를 반환시키자
  if (arr.length % 2 === 1) {
    answer = false;
    console.log("배열 홀수일 경우 : " + answer);
    return answer;
  }

  // 3. 최소 단위의 괄호부터 소거하여 , 제일 외각의 괄호까지 소거시키는 반복문을 실행
  let a = ""; // 좌측 문자 저장소
  let b = ""; // 우측문자 저장소
  let c = arr.length / 2; //배열 크기의 절반값을 저장
  // 배열 크기의 절반만큼 반복시킨다.
  for (let j = 0; j < c; j++) {
    for (let i = 0; i < arr.length; i++) {
      a = arr[i]; // a에 좌측 문자저장

      // 비교 우측 문자 b에 저장
      if (a === "(") b = ")";

      //쌍이 맞으므로 소거시킴
      if (arr[i + 1] === b) {
        arr[i] = " ";
        arr[i + 1] = " ";
        // 빈 요소로 만든 후 filter를 이용해 부분을 소거
        arr = arr.filter((item) => item !== " ");
        //for문 나가기
        break;
      }
    }
  }

  //  4. 반복문 완료 후에, 소거된 배열의 길이가 0이면 true , 0 초과면 falseㄹ르 반환시킨다.
  if (arr.length === 0) {
    answer = true;
  } else {
    answer = false;
  }
  console.log("배열 짝수일 경우 : " + answer);
  return answer;
}

(2) 스택 알고리즘 적용 후 나의 풀이

const check = (str) => {
  let answer = false;
  // 데이터를 쌓을 stack 배열
  let stack = [],
    cnt = 0;
  for (let x of str) {
    //열린 괄호인 경우 stack에 저장
    if (x === "(") {
      stack.push(x);
      //쌓인 요소의 갯수 측정
      cnt++;
    }
    // 닫힌 괄호인 경우 끝의 요소를 pop
    else {
      stack.pop();
      // 쌓이 요소 갯수 제거
      cnt--;
    }
  }
  //cnt가 0보다 크면 짝이 맞지 않은 것이므로 false
  if (cnt > 0) {
    answer = false;
    console.log(answer);
    return answer;
  }
  //여기까지 통과됐으면, 짝이 맞으므로 true
  answer = true;
  console.log(answer);
  return answer;
};

3. 느낀점

• 처음 내가 푼 방식도 어느정도 스택 자료구조 형태와 어느정도 유사하긴 한 것 같다.
• 확실히 자료구조를 공부하고 적용을 해보니, 내가 푼 방법보다는 좀 더 가독성면에서도 좋은 것 같다.
• 스택 외에도 여러 자료구조(큐,해시 테이블,연결 리스트 등)이 있으므로, 알고리즘 문제를 풀어나가면서, 하나씩 배워나가야겠다.

참고 링크

• https://velog.io/@ghldjfldj/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EB%9E%80
• https://breathtaking-life.tistory.com/107