[스택]올바른 괄호

문제

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

 

문제풀이

 

스택

• 스택(stack)은 제한적으로 접근할 수 있는 순차 리스트(나열) 자료 구조
• FIFO(First In Last Out) 선입 후출: 처음에 들어간 것이 나중에 나오도록 되어 있는 자료 구조
• 요소의 삽입과 삭제가 자료 구조의 한쪽 끝에서만 이루어지는 것이 특징
• push 연산: 자료구조 내에 비어 있는 끝 공간에 데이터 적재
• pop 연산: 자료구조 내에 끝에 있는 데이터를 삭제

---

---

괄호는 여는 괄호와 닫는 괄호가 한 쌍이다.

완전한 괄호가 되기 위해서는 각 괄호가 한 쌍이 이루어져야 한다. 

 

이를 위해 다음 그림과 같이 여는 괄호가 문자열 내에 나오면 자료구조에 적재한다. 이후에 여는 괄호가 연속적으로 나오게 된다면

계속해서 자료구조에 다음 인덱스에 적재한다. 

 

만약 닫는 괄호가 문자열 내에서 참조하게 될 경우 적재했었던 여는 괄호를 자료구조 내에서 없애준다.

이때 여는 괄호가 기존의 자료구조 내에 하나도 없다면 데이터를 없애주는 것이 아니라 현재 참조하고 있는 닫는 괄호를 자료구조 내에 적재해 준다.

 

위와 같은 연산을 문자열 끝까지 반복했을 경우 완전한 괄호일 경우에는 자료구조 내에는 어떠한 닫는 괄호가 존재해서는 안된다.

닫는 괄호가 자료구조 내에 하나라도 남아있다면 이는 한 쌍을 찾는 데 실패해서 남은 잔여 괄호가 있다는 점을 의미하기 때문이다.

 

코드

function solution(str) {
  let answer = "YES";
  let lp = "(";
  let rp = ")";
  let lpNum = 0; // 현재 남아 있는 lp(여는 괄호)의 갯수
  let checkArr = [];

  for(let x of str) {
    if(x === lp) {
      checkArr.push(1);
      lpNum++;
    }
    if(lpNum === 0 && x === rp) { //남아 있는 lp가 없을 경우_남아 있는 닫는 괄호를 적재
      checkArr.push(1);
    }
    if(lpNum > 0 && x === rp) { //남아 있는 lp가 있을 경우
      checkArr.pop();
      lpNum--;
    }
  }
  if(checkArr.length !== 0) answer = "NO";
  return answer;
}

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

---

function solution(str) {
  let answer = "YES";
  let stack = [];

  for(let x of str) {
    if(x === '(') stack.push(x);
    else {
      if(stack.length === 0) return "NO";
      stack.pop(x);
    }
  }
  if(stack.length > 0) return "NO";
  return answer;
}

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