[코플릿] 스택 Stack

✔️ 시작

알고리즘이 많이 부족하다 생각해
과제로 풀게 된 코드를 블로깅 하면서 공부하려고 한다.

작성한 코드는 아마 내가 작성했기 보단 레퍼런스 코드나 다른 사람이 작성한 코드에서
수도 코드를 작성하면서 어떻 형식으로 진행 했는지 파악하며 조금씩 익히려고 한다.

---

📍Stack - 유효한 괄호쌍

문제

입력된 괄호 값들이 모두 쌍이 맞게 올바른지를 판단해 모두 쌍이 맞으면 true 그렇지 않으면 false를 출력

입력된 괄호 값들이 유효한 경우들은 다음에 해당
1. 열린 괄호는 같은 타입의 닫힌 괄호로 닫혀있어야 한다.
2. 열린 괄호는 올바른 순서대로 닫혀야만 한다.
3. 모든 닫힌 괄호는 그에 상응하는 같은 타입의 열린 괄호를 갖고 있다.

입력값을 통해 들어오는 괄호는 ()[]{}로만 이루어져 있다.

입력
인자 1 : str
string 타입으로 된 문장

출력
boolean 타입을 리턴해야 합니다.

주의 사항
입력값을 통해 들어오는 괄호는 ()[]{}로만 이루어져 있습니다.
입력값으로 들어오는 str의 길이는 0부터 10^4승 까지 입니다.

힌트

• 스택을 사용해 보세요.
• 열린 괄호인 경우 스택에 push합니다.
• 닫힌 괄호인 경우에는 스택의 top을 확인하고, 해당 닫힌 괄호와 짝이 맞는 열린 괄호인지를 확인합니다.

const isValid = (str) => {
  // 예외 처리
  if(str.length === 0) return false
  // 괄호를 식별할 수 있는 객체 생성
  const obj = { '(': ')', '[': ']', '{': '}' }
  // str 배열로 반환하기
  const arr = str.split('')
  // 스택 초기화
  let stack = []

  // arr 순회
  for (let i in arr) {
    // 만약 arr[i]인 앞에 괄호인 경우
    if (arr[i] === '(' || arr[i] === '[' || arr[i] === '{') {
      // 스택에 추가해 둔다.
      stack.push(arr[i])
    // 뒤에 괄호인 경우
    } else {
      // 스택의 맨 위에 있는 요소를 기준으로 정해줌
      const top = stack[stack.length - 1]
      // 만약 arr[i]가 뒤에 괄호하고 일치 하지 않는다면 false 반환
      if(obj[top] !== arr[i]){
        return false
      }
      // 짝이 맞다면 스택에서 꺼낸다.
      stack.pop()
    }
  }
  // boolean을 반환해야하기 때문에 
  // stack의 값이 없을 경우 true, 아닌 경우 false
  return stack.length === 0
  /* 레퍼런스는 삼항 연산자를 사용 했다.
  return stack.length? false : true
  */
}

작성해본 의사코드

1. (str.length === 0)빈 값인 경우 false (예외 처리)
2. (obj) - obj에 괄호를 넣어줘 식별할 기준을 만들어 준다.
3. (arr) - str을 배열로 변수 선언해 준다. / (stack) - 스택을 초기화해 준다.
4. arr를 순회한다 (for문 사용)
5. 만약 arr가 시작하는 괄호인 경우 (stack.push) 스택에 추가해 준다.
6. 그렇지 않는 경우(닫는 괄호인 경우) 스택 맨 위에 있는 요소로
7. 현재 괄호와 짝이 맞는지 (obj[top]) 확인해 아닌 경우 false를 반환한다.
8. 맞을 경우 스택에서 꺼내 닫는 괄호를 제거해 준다.(stack.pop())
9. stack.length === 0으로 stack이 빈값인 경우 true를 반환한다.
   (조건이 맞을 경우 stack의 값을 전부 꺼냈기 때문)

💡 알게된 점

스택의 메서드

• size(): 스택에 저장된 데이터의 개수를 반환
• push(): 스택에 데이터를 추가
• pop(): 스택에서 최상위에 있는 데이터를 제거하고 반환
• top: 스택에서 최상위에 있는 데이터를 반환
• storage: 스택에 저장된 데이터를 저장하는 배열(Array)

왜 기준을 top = stack[stack.length - 1]으로 했을까

const top = stack[stack.length - 1] 

• stack[stack.length - 1] 뜻이 스택의 맨 위(top)에 있는 요소를 참조하는 것이다.
  - stack.length는 스택의 현재 길이를 나타내는데 스택의 요소가 없을 때 0이 된다.
  

stack[stack.length - 1]를 사용해 스택에서 가장 위에 있는 괄호를 꺼내온다.
꺼내온 괄호는 현재 문자열에서 처리 중인 닫는 괄호와 짝이 맞는지 검사할 때 사용한다.

---

✏️ 마치며

의사코드를 작성하면서 다시 코드를 보니 어느 정도 이해는 가지만
아직도 이해 안되는 부분은 chat GPT의 도움을 보면서 해결하고 있는거 같다.

꾸준히 하다보면 스스로 풀 수 있는 날이 오지 않을까 싶다.

자료 참고
chat GPT

문제 될 경우 삭제하겠습니다.