on
[백준알고리즘-JAVA]9012번 풀이(괄호) - 초보도 이해하는 풀이
[백준알고리즘-JAVA]9012번 풀이(괄호) - 초보도 이해하는 풀이
안녕하세요
인포돈 입니다.
백준 알고리즘 9012번 풀이입니다.
* 참고사항
- 개발환경은 eclipse을 기준으로 작성되었습니다.
- java언어를 이용하여 문제를 풀이합니다.
- 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
- 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.
백준 9012 (괄호)
문제
괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’와 ‘)’ 만으로 구성되어 있는 문자열이다. 그중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다.
여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO로 나타내어야 한다.
입력
입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 주어진다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다.
출력
출력은 표준 출력을 사용한다. 만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다.
입력, 출력 예제
성공 코드
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Stack; import java.util.StringTokenizer; public class Main { static int T; static StringBuilder sb = new StringBuilder(); public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); T = Integer.parseInt(br.readLine()); for(int i = 0 ; i < T ; i++) { char[] temp = br.readLine().toCharArray(); int check = 0; for(char a : temp) { if(check >= 0) { if(a == '(') { check += 1; }else if(a == ')'){ check -= 1; } }else { break; } } if(check == 0) sb.append("YES").append("
"); else sb.append("NO").append("
"); } System.out.println(sb); } }
이번 알고리즘을 풀기 앞서서 간략히 힌트를 하나 드리고자 합니다. 저 같은 경우는 STACK문제이니 스택을 사용하는 게 맞지만, 보고 나서 딱 떠올린 방법이 있습니다. 괄호가 열릴 경우 + 닫힌 경우 -을 활용하여 이를 판별했단 것을 알려드립니다 ㅎㅎ
STEP을 보기전에 힌트만 보고 풀어보는 것도 도움이 됩니다~
알고리즘 흐름도
입력 받기 -> CHECK 판별하기 -> 출력하기
STEP1 입력받기 및 check 초기화
for(int i = 0 ; i < T ; i++) { char[] temp = br.readLine().toCharArray(); int check = 0; }
네 아주 간단합니다. 입력을 char로 받아 버린 다음 check 변수를 0으로 초기화해줍니다.
STEP2 check 판별하기
for(int i = 0 ; i < T ; i++) { char[] temp = br.readLine().toCharArray(); int check = 0; for(char a : temp) { if(check >= 0) { if(a == '(') { check += 1; }else if(a == ')'){ check -= 1; } }else { break; } } }
우선 입력받은 temp로부터 하나식 꺼내옵니다. check를 확인 후 0 이상이면 해당 조건문을 통과합니다..
0 이상이라는 의미는 열기 전에 닫힌 괄호가 없다는 의미!
여기에서 이제 판별해줍니다 닫힌 괄호인지 열린 괄호인지, 만약 열린 괄호라면 +1을 아니라면 -1을 해줍니다.
(여기서 첫 번째 if문인 0 이상 조건에 걸리지 않으면 break로 해당 문을 빠져나가 바로 NO가 출력되게 한다.)
STEP 3 출력하기
출력하기야 뭐 앞서 판별한 CHECK를 통해서 값이 0이라면 YES 아니라면 NO를 출력해 주면 끝~
for(int i = 0 ; i < T ; i++) { char[] temp = br.readLine().toCharArray(); int check = 0; for(char a : temp) { if(check >= 0) { if(a == '(') { check += 1; }else if(a == ')'){ check -= 1; } }else { break; } } if(check == 0) sb.append("YES").append("
"); else sb.append("NO").append("
"); }
from http://infodon.tistory.com/93 by ccl(A) rewrite - 2021-09-20 11:27:53