프로그래머스_올바른 괄호

🪧 괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어

• "()()" 또는 "(())()" 는 올바른 괄호입니다.
• ")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.

'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

제한사항

• 문자열 s의 길이 : 100,000 이하의 자연수
• 문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.

입출력 예

s	answer
"()()"	true
"(())()"	true
")()("	false
"(()("	false

• 구상한 알고리즘 괄호 개수만 생각해서 풀면 X (( )) 이런 식으로 무조건 닫혀야 함

  1. ) 가 먼저 나오면 무조건 X

  2. 무조건 시작은 ( 여야 하고, ( 개수 세고 ) 가 ( 개수 만큼 나와야 함

     빼다가 ( 개수 세고 ) 는 ( 개수 만큼 나와야 하므로

  • 만약 그렇지 않다면 FALSE
  • ) 로 시작해도 FALSE
  • 다 하고 난 뒤 Stack이 empty가 아니면 FALSE
• 정답 알고리즘
  • ( 를 만나면 Stack에 집어넣고, ) 를 만나면 ( 를 Stack에서 pop 한다
  • 만약 Stack이 비어있는 상태라면 올바른 괄호가 아니다.
  • 다 돌았을 때, Stack이 비어있지 않다면 올바른 괄호가 아니다.
• 실패 원인 String을 CharAt으로 일단 Stack에 모두 push하고 꺼내면서 비교하는 방식으로 생각하여 알고리즘을 설계하다가 꼬였음. → 애초에 알고리즘 구상 잘못함. 그리고 Java 문법에 익숙치 않아 구글링 하다 시간을 허비했음.
  
• ⭐풀이 코드⭐

  package correctParentheses;
  import java.util.Scanner;
  import java.util.Stack;
  
  public class Solution {
      public boolean solution(String s) {
          boolean answer = true;
          Stack<Character> stack = new Stack<>();
          for(int i = 0; i<s.length(); i++){
              char c = s.charAt(i);
              if(c == '(')
                  stack.push(c);
              else{
                  if(stack.size()==0)
                      answer = false;
                  else
                      stack.pop();
              }
          }
          if(stack.size()!=0)
              answer = false;
  
          return answer;
      }
  
  }

  • import java.util.Stack;
  • Stack stack = new Stack<>();
  • char c = s.charAt(i); 로 괄호 분리하여 push or pop