문제 📕

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

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

(https://www.acmicpc.net/problem/9012)

접근 방법 🧐

이전에는 문제 하단에 있는 알고리즘 분류를 꼭 보고 문제를 풀었지만, 요새는 안 보고 풀려고 노력하고 있다!! 하지만 도저히 모를 때는 보고 있다 헿

문제를 읽으며 드는 생각을 적어보고 있다.

1. 스택을 사용해야겠구나
2. 입력 한 것을 String으로 한 줄 씩 읽고, 해당 괄호 문자열이 VPS 인지 확인해야한다
3. StringBuilder 변수에 "YES", "NO"를 append 해줄 것이다.
4. "(" 이면 push 하고
   • 반복문을 다 돌렸는데 empty=false이면 "NO" 임
5. ")" 이면 pop 해야한다
   • pop할게 없으면 "NO" 임

내가 쓴 코드 ✍️

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int cnt = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		for(int i=0;i<cnt;i++) {
			String str = br.readLine();
			Stack<Character> stack = new Stack<>();
			Boolean vps = true;
			for(int j=0;j<str.length();j++) {
				char c = str.charAt(j);
				
				if(c=='(') {
					stack.push(c);
				}
				else if(stack.empty()) {
					vps = false;
					break;
				}
				else {
					stack.pop();
				}
			}
			if(!stack.isEmpty()||!vps) {
				sb.append("NO\n");
			}
			else {
				sb.append("YES\n");
			}
			
		}
		
		bw.write(sb+"");
		bw.flush();
		bw.close();
	}

}

느낀점 📖

아직도 stack 메소드를 헷갈려하면 쓰겠나,, 당장의 문제를 푸는 것으로 넘기지 말고 자연스럽게 나오도록 익히자