[백준알고리즘-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("\n");
			else
				sb.append("NO").append("\n");
			
		}
		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("\n");
			else
				sb.append("NO").append("\n");
			
		}