[BOJ] 9012_ 괄호

eeeeu·2022년 4월 29일
0

Algorithm review book

목록 보기
1/12

문제

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다.

여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다.

예제 입력

3
((
))
())(()

예제 출력

NO
NO
NO

문제바로가기


Key Point

  1. stack을 사용하자
    stack을 구현할 필요 없이 Stack의 크기만 이용해서 풀이가능

풀이

'('는 괄호를 만났을때 stack에 넣어주자.
언제 "NO"가 나오게 되는지 생각해보자.
1. 닫는 괄호( ')' )를 만났는데, 스택이 비었는 경우
2. 끝났는데 스택이 비지 않았을 경우

배운점

나는 main() 함수 안에 코드를 전부 적었는데, 함수를 구현해서 호출하면 훨씬 깔끔해진다는 것을 왜 진작 활용을 못 했을까,,
함수를 구현해서 문제를 푸는 습관을 길러야겠당

코드

import java.io.*;
import java.util.*;

public class ParenthesisMJ {
  public static void main(String[] args) throws IOException {
      Scanner sc = new Scanner(System.in);
      BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
      int n=sc.nextInt();

      while (n-- >0)
      {
          String cmd=sc.next()+"\n";
          int top=0;
          for (char ch: cmd.toCharArray())
          {
              if (ch=='(')
                  top++;
              else if (ch==')')
              {
                  if (top<=0)
                  {
                      bw.write("NO\n");
                      break;
                  }
                  top--;
              }
              else if (ch=='\n')
              {
                  if (top==0)
                      bw.write("YES\n");
                  else
                      bw.write("NO\n");
              }
          }

      }
      bw.flush();
      bw.close();
  }
}
profile
라따뚜이 인생이란

0개의 댓글