[스택] 백준 - 9012

BOJ/백준 9012 - 괄호

해당 문제는 스택을 사용해서 안풀어도 되지만 스택을 사용해서 풀면 편하게 해결할 수 있다.
스택에 대해서 모른다면
자료구조 - Stack 사용법을 읽고 오자!

---

백준 9012 - 괄호

1. 문제 분석

문제 이해

괄호 문자열 PS는 '(' 와 ')'로 구성된 문자열 / 그 중에서 한 쌍의 괄호 기호로 된 "()"은 기본 VPS
즉, 쌍이 잘 이루어진 괄호는 VPS, 쌍이 잘 이루어지지 못한 괄호는 VPS가 아닌 문자열
테스트 데이터의 괄호 문자열이 VPS이면 YES 아니면 NO

입력

• T개의 테스트 데이터로 주어짐
• 각 테스트 데이터의 첫째 줄에는 괄호 문자열 길이는 2 이상 50 이하

출력

• 입력 문자열이 올바른 괄호 문자열(VPS)이면 "YES" 아니면 "NO"

2. 시간 복잡도

• 테스트 케이스 T 만큼 반복하니까 → O(T)
• 문자열 ps의 길이 만큼 반복하니까 → O(N)
• stack의 핵심 연산 push(), pop(), isEmpty() 들은 → O(1) 상수 시간

하나의 테스트 케이스를 처리하는데 O(N)의 시간이 필요하다
따라서, O(N)의 작업을 T수 만큼 반복하니까 총 시간 복잡도는 O(N * T)

3. 코드 구현

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

public class No_9012 {
	public static void main(String args[]) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		
		for(int i = 0; i < T; i++) {
			String ps = br.readLine();
			Stack<Character> stackStr = new Stack<>();
			boolean isVPS = true;
			
			for(int j = 0; j < ps.length(); j++) {
				char s = ps.charAt(j);
				
				if (s == '(') {
					stackStr.push(s);
				} else if(s == ')') {
					if(stackStr.isEmpty()) {
						isVPS = false;
						break;
					} else {
						stackStr.pop();
					}
				}
			}
			
			if(!stackStr.isEmpty()) {
				isVPS = false;
			}
			
			if (isVPS) {
				sb.append("YES").append("\n");
			} else {
				sb.append("NO").append("\n");
			}
		}
		System.out.println(sb);
	}
}

---

알고리즘 해결

1. 우선 String ps를 입력 받기
2. ps의 문자열에서 한 문자씩 검사
   2-1. '(' 이면, stack.push()
   2-2. ')' 이면서 stack이 비어있다면 isVPS 값을 false 값으로 바꾸고 for문 중지
   2-3. ')' 이면서 stakc이 안 비어있다면 stack.pop()
3. stackStr이 비어있지 않으면 여는 괄호가 남은거니까 isVPS가 false로 바뀜
4. isVPS가 true면 YES, false면 NO