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

 

https://hyejin.tistory.com/1231

자바 알고리즘 문제 풀이 입문. 섹션4. HashMap, TreeSet (해쉬, 정렬지원 Set) : K번째 큰 수 (TreeSet)

-> 이전 문제 풀이 

 

 

 

1. 올바른 괄호 

설명

괄호가 입력되면 올바른 괄호이면 “YES", 올바르지 않으면 ”NO"를 출력합니다.

(())() 이것은 괄호의 쌍이 올바르게 위치하는 거지만, (()()))은 올바른 괄호가 아니다.

 

입력

첫 번째 줄에 괄호 문자열이 입력됩니다. 문자열의 최대 길이는 30이다.

 

출력

첫 번째 줄에 YES, NO를 출력한다.

 

예시 입력 1 

(()(()))(()

 

예시 출력 1

NO

 

문제 풀이 1

public String solution(String s)
{
   String answer = "NO";
   Stack<Character> stack = new Stack<>();
   
   for (char c : s.toCharArray())
   {
      if (c == '(') {
         stack.push(c);
      }
      else if (c == ')') {
         if (stack.size() != 0) {
            if (stack.peek() == '(')
            {
               stack.pop();
            }
         }else {
            stack.push(c);
         }
      }
   }
   
   if (stack.size() == 0)
      return "YES";
   
   return answer;
}

👩‍💻 : 이 문제는 예전에 프로그래머스에서 한번 해봤던 기억이 있는 문제이다. 

보통 Stack 으로 알고리즘 문제 낼 때 괄호 관련 문제가 꼭 나온다고 한다.  ㅎㅎ (참고) 

 

일단 이 문제는 문자열이 주어지면 그 문자열의 괄호가 올바른 괄호이면 YES 리턴 아니면 NO 리턴하는 문제이다. 

 

예시 입력

(()(()))(()

을 보면 '(' 하나 남기 때문에 올바른 괄호가 아니라서 답은 NO가 출력되어야 한다. 

 

우선 Character 문자를 담는 Stack 을 만들고, 주어진 문자열을 문자 배열로 반복문 돌려서 해당 문자가 '(' 이면 stack에 넣고, ')' 이면 stack에서 pop 해주면 된다. 

근데 이때 stack이 비어있는 경우에 pop을 하려고 하면 에러가 발생할 것이다. (없는데 pop하려고 해서) 그러므로 stack.size가 0이 아니고, stack의 값이 '(' 일 경우에 pop을 하도록 한다. 

그리고 만약 stack.size가 0이면 stack에 ')' 값을 넣어주도록 했다. (이 부분은 굳이 안해도 됐을 텐데,.) 

 

이렇게 반복문을 다 돌고 나서 stack의 size가 0이면 올바른 괄호라는 뜻이기 때문에 YES를 리턴하면 되고

size가 0이 아니라면 그대로 NO를 리턴한다. 

 

 

문제 풀이 2

public String solution2(String str)
{
   String answer = "YES";
   Stack<Character> stack = new Stack<>();
   
   for (char x : str.toCharArray())
   {
      if (x == '(') {
         stack.push(x);
      } else {
         if (stack.isEmpty()) { // 닫는 괄호 ')'가 많은 상황
            return "NO";
         }
         stack.pop();
      }
   }
   
   if (!stack.isEmpty()) // 여는 괄호 '(' 가 많은 상황
      return "NO";
   
   return answer;
}

👾 : 강사님은 이 문제를 더 간단하게 풀었다. 우선 주어진 문자열을 문자 배열로 만들어서 for문 돌려  stack에 넣는 건 동일하다. 우선 char x 가 '(' 이면 stack에 push 하고, ')' 이면 stack에서 pop 하면 된다. 근데 이때 마찬가지로 stack이 비어 있으면 ')'가 더 많다는 의미이므로 이때는 바로 return NO 해주면 된다. 그리고 stack이 비어있지 않다면 stack에서 ')' 값을 'pop' 해주면 된다. 

 

반복문을 다 돌고 나서 stack이 비어있는지 한번 더 검사를 하는데 이때 비어있지 않다는 것은 '('의 개수가 더 많아서 올바른 괄호가 아니라는 뜻이기 때문에 NO를 리턴해준다. 

 

그리고 마지막으로 stack이 비어있다면 그건 올바른 괄호라는 말이기 때문에 YES 를 리턴해주면 된다.