[Baekjoon] 8594_Program

문제(출처: https://www.acmicpc.net/problem/8594)

---

< Program >

 

문제 풀이 

 

열린 괄호는 stack에 넣고, 닫힌 괄호는 stack에서 일치하는 쌍인지 확인 후 제거한다. 이때, 모든 괄호가 유효하다면 stack의 최대 size를 정답으로 출력한다.

 

my solution (Java)

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

public class _8594_ { // Program

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(bf.readLine());
		String str = bf.readLine();

		Stack<Character> stack = new Stack<>();
		int result = 0;
		boolean flag = false;
		for (int i = 0; i < n; i++) {
			if (str.charAt(i) == '(' || str.charAt(i) == '[' || str.charAt(i) == '{') {
				stack.add(str.charAt(i));
				result = Math.max(result, stack.size());
			} else if (str.charAt(i) == ')') {
				if (stack.size() > 0 && stack.peek() == '(') {
					stack.pop();
				} else {
					flag = true;
					break;
				}
			} else if (str.charAt(i) == ']') {
				if (stack.size() > 0 && stack.peek() == '[') {
					stack.pop();
				} else {
					flag = true;
					break;
				}
			} else if (str.charAt(i) == '}') {
				if (stack.size() > 0 && stack.peek() == '{') {
					stack.pop();
				} else {
					flag = true;
					break;
				}
			}
		}
		if (flag || stack.size() > 0) {
			System.out.println("NIE");
		} else {
			System.out.println(result);
		}
	}
}

변수)
n : 프로그램의 길이
str : 단어
stack : 열린 괄호를 저장하는 Stack
result : 최대 중첩 괄호 수
flag : 유효 여부

 

프로그램 길이와 단어를 입력받는다. 단어를 탐색하면서 열린 괄호라면 stack에 저장한다. 이때, result를 stack의 size와 비교하여 최댓값으로 업데이트한다. 닫힌 괄호라면 stack에서 일치하는 쌍인지 확인 후 일치하다면 stack에서 제거한다. 일치하지 않다면 유효하지 않은 단어이므로 flag를 true로 저장 후 종료한다.

 

최종 flag가 true이거나 stack이 비어있지 않다면 유효하지 않은 단어이므로 NIE를 출력하고, 유효하다면 최대 중첩 괄호 수인 result를 출력한다.

---

---