자바스크립트 stack 괄호 짝 찾기 문제 풀이

문제 설명

- 같은 짝의 괄호 위치를 찾아 출력

- 입력은 계산 수식으로 주어지며, 괄호의 짝 별 위치를 [시작, 끝] 으로 찾아 2차원 배열 형태로 반환

- 위치 시작 값은 0으로 시작, 하나라도 짝이 맞지 않을 경우 빈 배열을 반환한다.

 

입력 값

-    "(a+b)"
-    "(a*(b+c)+d)"
-    "(a*(b+c)+d+(e)"
-    "(a*(b+c)+d)+e)"
-    "(a*(b+c)+d)+(e*(f+g))"

 

출력 값

#1 [ [ 0, 4 ] ]
#2 [ [ 3, 7 ], [ 0, 10 ] ]
#3 []
#4 []
#5 [ [ 3, 7 ], [ 0, 10 ], [ 15, 19 ], [ 12, 20 ] ]

- 2차원 배열에 넣어야하는게 처음에 문제가 어려웠다..

- 빈 배열을 넣고 따로 문제를 계산해서 인덱스를 넣을 생각을 했었다.

 

 

 

문제 풀이

if (!Array.prototype.isEmpty) {
  Array.prototype.isEmpty = function () {
    return this.length === 0;
  };
}

function answer(str) {
  let result = [];
  let stack = [];
  for (let i = 0; i < str.length; i++) {
    if (str[i] == "(") {
      stack.push(i);
    } else if (str[i] == ")") {
      if (stack.isEmpty()) {
        return [];
      }
      result.push([stack.pop(), i]);
    }
  }
  if (!stack.isEmpty()) return [];
  return result;
}

- 빈배열을 가진 stack변수를 만들었다.

- 반복문을 통해서 str.length만큼 순회한다.

- 만약 str[i]가 "("와 같다면 stack에 index값을 넣어준다. // index값을 출력해야하기 때문에 바로 index를 넣으면 된다.

- 만약 str[i]가 ")"와 같다면 stack.length가 0이면 빈 괄호[]를 반환한다. // 처음 조건문에서 "("를 stack에 push를 했기 때문에 length가 0이라면  같은짝이 없다.

- stack.length가 0이상 이라면 result에 []안에다가 stack에 있는 index를 pop으로 빼고 현재 ")"인 index를 같이 []안에 넣어준다.

- 이렇게 모든 반복문을 실행하고도 stack 이 빈배열이 아니라면 []빈괄호를 반환한다.

 

for문과 if문으로 간단하게 풀 수 있는 문제였다. []안에서 stack.pop을 하는게 처음에는 생각을 못했었다ㅠㅠ