TIL. 스택 알고리즘 문제 풀이

스택

스택(Stack)은 후입선출(Last In First Out, LIFO)의 원리로 작동하는 자료구조이다.
즉, 가장 마지막에 추가된 요소가 가장 먼저 제거된다. 스택은 알고리즘과 프로그램의 다양한 부분에서 활용되며, 데이터를 임시 저장하고 순서대로 처리해야 하는 다양한 상황에서 유용하게 사용된다.

• 스택은 데이터를 임시 저장하기 위한 선형 자료구조로, 데이터의 추가(푸시), 삭제(팝), 최상위 요소 확인(피크) 등의 기본적인 작업을 지원한다.

• 스택은 책을 쌓아 놓은 것과 비슷하게, 새로운 책을 위에 올려놓고, 책을 가져갈 때는 가장 위에 있는 책부터 가져가는 방식으로 작동한다.

📌 선형 자료구조란?
선형 자료구조는 데이터를 순차적으로 나열한 구조를 말한다.

이러한 구조에서는 데이터 항목들이 연속적인 위치에 저장되며, 각 데이터 항목은 단 하나의 선행 요소와 후속 요소를 가진다(첫 번째와 마지막 요소는 각각 선행 요소나 후속 요소가 없을 수 있다).

선형 자료구조의 대표적인 예로는 배열, 연결 리스트, 스택, 큐 등이 있다. 이들은 모두 데이터를 선형적으로 처리하고 저장하는 방식을 사용한다.

📌 최상위 요소 확인 (피크)
스택에서 최상위 요소 확인(피크, Peek)는 스택의 가장 위에 있는 요소를 제거하지 않고 반환하는 연산을 말한다.
이는 스택에 저장된 가장 최근의 데이터를 확인할 때 사용되며, 스택의 상태를 변경하지 않는다.
피크 연산은 스택의 사용 사례에 따라 필수적일 수 있으며, 스택에 저장된 데이터를 조회하는데 사용된다. 예를 들어, 사용자가 어떤 작업을 실행하기 전에 스택의 최상위 요소를 먼저 확인하고 싶을 때 피크 연산을 사용할 수 있다.

📌 스택의 기본적인 작업
푸시(Push): 스택의 최상단에 새로운 요소를 추가
팝(Pop): 스택의 최상단에 있는 요소를 제거하고, 그 요소를 반환
피크(Peek): 스택의 최상단에 있는 요소를 제거하지 않고 확인

스택은 이러한 작업을 통해 LIFO(Last In, First Out) 원칙을 따르며 데이터를 관리한다. 데이터를 추가하고 제거하는 방식이 선형적으로 이루어지기 때문에, 스택은 선형 자료구조의 한 종류로 분류된다고 한다. 🧐

스택을 활용한 알고리즘 예시

괄호 검사 알고리즘
: 여는 괄호를 만날 때마다 스택에 푸시하고, 닫는 괄호를 만날 때마다 스택에서 팝하여 짝을 지어 검사한다. 이 과정에서 스택이 비어있거나 검사를 마친 후 스택에 요소가 남아 있으면 괄호가 올바르지 않은 것으로 판단한다.

역순 문자열 생성
: 문자열의 각 문자를 차례대로 스택에 푸시하고, 모든 문자가 스택에 들어간 후에 스택에서 팝하는 순서대로 새 문자열을 생성하면 원본 문자열의 역순을 얻을 수 있다.

스택 활용 예

함수 호출과 실행 컨텍스트 관리
: 대부분의 프로그래밍 언어에서 함수 호출 시 스택을 사용하여 호출 정보(반환 주소, 매개변수, 지역 변수 등)를 저장한다. 함수가 호출되면 그 정보가 스택에 푸시되고, 함수가 종료되면 스택에서 팝된다. 이를 통해 프로그램의 실행 컨텍스트를 관리한다.

프로그램의 실행 취소(Undo) 기능
: 문서 편집기, 그래픽 소프트웨어 등에서 사용자의 동작을 스택에 저장함으로써 실행 취소(Undo) 기능을 구현할 수 있다. 사용자가 취소 명령을 내리면 스택에서 최근 동작을 팝하여 변경 사항을 되돌린다.

웹 브라우저의 세션 기록 관리
: 웹 브라우저는 사용자가 방문한 페이지의 이력을 스택으로 관리할 수 있다. 사용자가 새 페이지로 이동할 때마다 해당 페이지의 주소를 스택에 푸시하고, 사용자가 '뒤로 가기'를 클릭하면 스택에서 주소를 팝하여 이전 페이지로 돌아간다.

1. 올바른 괄호

문제 설명

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

▣ 입력설명
첫 번째 줄에 괄호 문자열이 입력된다. 문자열의 최대 길이는 30이다.

▣ 출력설명
첫 번째 줄에 YES, NO를 출력한다.

▣ 입출력 예

input	output
(()(()))(()	NO
((())((()())))	YES

풀이

1차시도

const correctParentheses = (a) => {
  if (a[0] === ')') return 'NO';

  let stack = [];

  for (let i = 0;    i < a.length; i++) {
    stack.push(a[i]);
    if (a[i] === ')') {
      stack.pop(a[i]);
      stack.pop(a[i - 1]);
    }
  }

  if (stack.length > 0) return 'NO';
  return 'YES';
};

let a = '(()(()))(()';
console.log(correctParentheses(a));

👉 pop() 메서드의 사용법이 잘못되었다.

• pop 메소드는 배열에서 마지막 요소를 제거하고 그 값을 반환한다. 따라서 pop 메소드에 인자를 전달하는 것은 올바른 사용 방법이 아니다.😓 대신, 단순히 pop을 호출하여 가장 최근에 추가된 '('를 제거하기!

2차시도

const correctParentheses = (a) => {
  if (a[0] === ')') return 'NO';

  let stack = [];

  for (let i = 0; i < a.length; i++) {
    if (a[i] === '(') {
      stack.push(a[i]);
    } else if (a[i] === ')' && stack.length === 0) {
      return 'NO';
    } else {
      stack.pop();
    }
  }

  if (stack.length > 0) return 'NO';
  return 'YES';
};

let a = '((())((()())))';
console.log(correctParentheses(a));

• 괄호 문자열 a에 가장 처음으로 들어온 괄호 닫는형태 ) 라면 바로 빠른 return을 한다.
• 여는 괄호 ( 를 만날 때마다 스택에 추가하고, 닫는 괄호 ) 를 만날 때 스택에서 하나를 제거한다.
• 닫는 괄호 ) 를 만났을 때 스택이 비어있으면, 즉 짝을 이루는 여는 괄호가 없으면 바로 'NO'를 반환한다.
• 모든 검사를 마친 후 스택에 여는 괄호가 남아 있다면, 이는 모든 괄호가 올바르게 짝지어지지 않았음을 의미하므로 'NO'반환 한다.
  그렇지 않으면 'YES'를 반환한다.😀

✍️ solution

function solution(s) {
  let answer = 'YES';
  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));

2. 괄호문자제거

문제 설명

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

▣ 입력설명
첫 줄에 문자열이 주어진다. 문자열의 길이는 100을 넘지 않는다.

▣ 출력설명
남은 문자만 출력한다.

▣ 입출력 예

input	output
(A(BC)D)EF(G(H)(IJ)K)LM(N)	EFLM

풀이

const removeParenthesisCharacters = (str) => {
  let stack = [];

  for (let s of str) {
    stack.push(s);

    if (s === ')') {
      while (stack.length > 0 && stack.pop() !== '(');
    }
  }

  return stack.join();
};
let str = '(A(BC)D)EF(G(H)(IJ)K)LM(N)';
console.log(removeParenthesisCharacters(str));

👉 계획

• stack 배열에 받아온 문자열을 하나씩 차례대로에 넣는다.
• 이때 닫는괄호 ) 가 등장하면 여는괄호가 나올때까지 pop을 한다.
• 여는괄호 ( 가 나오는 순간 멈추고 다시 하나씩 문자를 넣는다.
  '멈춘다'에 초점을 맞추지말자 while문은 그 안에서 조건이 맞을때까지 while을 돌린다. 조건이 안맞는순간 알아서 다음 행으로 넘어가니까 return과 관련없다. 😓
• stack 배열에 가장 마지막에 남은 값들을 join() 해서 문자열로 출력한다.

while 문에서...
✍️ stack.length > 0 : 길이가 0이상일 때만 pop을 해야하므로
✍️ stack.pop() : )일때도 해당되므로 )을 따로(중복으로)pop하지 않도록 주의하자.

✍️ solution

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));

✍️ solution 처럼 stack.push(s) 를 else 뒤에 넣어주는 게 더 좋겠다.🧐 (불필요한 push 감소)