자바 알고리즘 문제 풀이 입문. ch05. Stack, Queue (자료구조) : 괄호 문자 제거

 

https://hyejin.tistory.com/1232

자바 알고리즘 문제 풀이 입문. ch05. Stack, Queue (자료구조) : 올바른 괄호

-> 이전 문제 풀이 

 

 

 

2. 괄호 문자 제거 

설명

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

 

입력

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

 

출력

남은 문자만 출력한다.

 

예시 입력 1 

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

 

예시 출력 1

EFLM

 

 

문제 풀이 1

public String solution(String str)
{
   String answer = "";
   Stack<Character> stack = new Stack<>();
   
   for (char c : str.toCharArray())
   {
      if (c == '(')
      {
         stack.push(c);
      } else if (c == ')'){
         stack.pop();
      } else {
         if (stack.isEmpty()) answer += c;
      }
   }
   
   return answer;
}

👩‍💻 : 이 문제는 이 전 풀이와 거의 비슷하게 풀 수 있다. 괄호 안에 있는 문자는 stack에 넣지 않고, '(' 를 stack에 push 했다가 ')' 를 만나면 pop 하면 되고, '('와 ')'가 아닐 때, stack이 비어있다는건 괄호 문자가 제거되었다는 얘기이므로 그 때는 answer 문자열에 문자를 더하면 된다. 

 

 

 

문제 풀이 2

public String solution2(String str)
{
   String answer = "";
   Stack<Character> stack = new Stack<>();
   
   for (char c : str.toCharArray())
   {
      if (c == ')') {
         while (stack.pop() != '('); // pop은 꺼내고 그 꺼낸값을 반환한다.
      }else
      {
         stack.push(c);
      }
   }
   
   for (int i = 0; i< stack.size(); i++)
   {
      answer += stack.get(i);
   }
   
   return answer;
}

👾 : 강사님은 우선 ')' 아닌 문자는 stack에 모두 push 하고, 그 다음에 ')' 이면 stack에서 이제 pop를 해주는데 

이때 pop() 메서드는 stack에서 꺼낸 다음, 해당 꺼낸 객체를 반환한다. 따라서 pop를 하고 반환한 문자가 '(' 이면 '(' 과 ')' 사이에 있는 문자까지 모두 pop 했다는 것이기 때문에 while (stack.pop() != '(')) 로 조건문을 걸어주면 된다. 

stack.pop() == '(' 라는 건 '(' 까지 pop 했다는 것이다. 

 

그 다음 stack을 반복문으로 돌면서 stack.get(i)를 통해 값을 꺼내고 answer에 더해주면 된다.