[JS] 코딩 테스트 문제 : 괄호 문자 제거 [스택]

문제 : 괄호 문자 제거

문제 설명

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

▣ 입력설명

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

▣ 출력설명

남은 문자만 출력한다.

▣ 입력예제 1

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

▣ 출력예제 1

EFLM

내코드

function solution(s) {
  let answer;
  let stack = [];

  // 문자열만큼 순회
  for (let i = 0; i < s.length; i++) {
    let word = s[i];

    // 현재 문자가 ")" 인 경우
    if (word === ")") {
      // j : stack 의 lastIndex 를 의미
      let j = stack.length - 1;

      // 현재 스택에서 부터 "("  나오기 전까지의 문자를 삭제
      while (stack[j--] !== "(") {
        stack.pop();
      }

      // "(" 문자 추출
      stack.pop();
      continue;
    }

    // 현재 문자가 ")" 아닌 모든 문자를 stack 에 push 해 저장
    stack.push(word);
    console.log(stack);
  }

  // 문자열로 치환
  answer = stack.join("");
  return answer;
}

let str = "(A(BC)D)EF(G(H)(IJ)K)LM(N)";
console.log(solution(str));

풀이

1. 문자열 만큼 순회 하면서 현재 문자가 ")" 아닌 모든 경우에 문자를 stack 에 추가
2. 현재 문자가 ")" 인 경우 stack 배열을 순회해 "(" 나오는 부분까지 pop 해 stack 에서 제외함으로써 괄호 안에 존재하는 문자와 괄호 모두 stack 에서 제외
3. 결과적으로 괄호 안에 존재하지 않는 문자들만 stack 에 남아있으므로 문자열로 변경해 반환

보완할 수 있는 부분

// 기존코드
for (let i = 0; i < s.length; i++) {
  let word = s[i];

  // 현재 문자가 ")" 인 경우
  if (word === ")") {
    // j : stack 의 lastIndex 를 의미
    let j = stack.length - 1;

    // 현재 스택에서 부터 "("  나오기 전까지의 문자를 삭제
    while (stack[j--] !== "(") {
      stack.pop();
    }

    // "(" 문자 추출
    stack.pop();
    continue;
  }

  // 현재 문자가 ")" 아닌 모든 문자를 stack 에 push 해 저장
  stack.push(word);
  console.log(stack);
}

// 보완코드
for (let x of s) {
  if (x === ")") {
    // stack 에서 pop 하여 꺼낸 값이 "(" 나오는지 체크 한 후 앞선 pop 하여 체크하는 과정을 반복해
    // 결과적으로 stack 에서 괄호사이의 문자들이 제외
    while (stack.pop() !== "(");
  } else stack.push(x);
}

---

참고

https://www.inflearn.com/course/%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4/dashboard