[Baekjoon] 5872_Clumsy Cows

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

---

< Clumsy Cows >

 

문제 풀이 

 

stack을 사용하여 균형 잡힌 괄호 문자열을 만들기 위해 뒤집어야 하는 최소 괄호 개수를 구한다.

 

1) ')'일 때 stack이 비어있다면 균형 잡힌 문자열이 아니므로 뒤집어야 한다.

2) 문자열 탐색이 끝난 뒤 stack에 값이 남아있다면 균형 잡힌 문자열이 아니므로 stack의 크기 / 2를 뒤집어야 한다.

 

my solution (Java)

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

public class _5872_ { // Clumsy Cows

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

		String str = bf.readLine();

		Stack<Character> stack = new Stack<>();
		int result = 0;

		for (int i = 0; i < str.length(); i++) {
			if (str.charAt(i) == '(') {
				stack.add(str.charAt(i));
			} else {
				if (!stack.isEmpty()) {
					stack.pop();
				} else {
					result += 1;
					stack.add('(');
				}
			}
		}
		if (!stack.isEmpty()) {
			result += stack.size() / 2;
		}
		System.out.println(result);
	}
}

변수)
str : 문자열
result : 뒤집어야 하는 최소 괄호 개수
stack : '('를 저장하는 Stack

 

문자열을 입력받아 탐색한다. 

1) '('일 경우 stack에 저장

2) ')'일 경우 stack이 비어있다면 뒤집어서 저장, stack이 비어있지 않다면 stack pop

 

탐색이 끝난 뒤 stack이 비어있지 않다면 stack size의 절반을 뒤집는다. 최종 result를 출력한다.  

---

---