標準4889、安定した文字列-文字列、stack

https://www.acmicpc.net/problem/4889

1.アイデア

入力文字列ごとにチェック

1)左かっこ{プッシュStack2)括弧}

Stack非空(左かっこ付き)
=>Stack左かっこ+右かっこに一致するようにポップアップ

Stackが空
=>Stackの右かっこ}を左かっこ{pushに置き換え、演算回数+1

3)入力文字列の全ての文字のチェックを終了する

Stack偶数個のみ左かっこ{=>大かっこ{:入力文字列の元の大かっこ{or文字列の括弧}を入力し、Stackに変換すると

を入力します.

演算回数+=(Stackのsize/2)
=>Stackの残りの左かっこ.
いずれかをカッコの半分だけを閉じるように置き換えると、残りのカッコはすべて完了

に一致します.
カッコの問題はいつもStackを思い出させる

2.資料構造

String:入力文字列

Stack<Character>:かっこ対マッチング

3.時間複雑度

各テストエンクロージャ(文字列)のO(len)
=>文字列あたり最大2000

コード#コード#

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

public class Main {
	static String str;			// 입력 문자열
	static Stack<Character> stack;

	static int solution(String str) {
		stack = new Stack<>();
		int minCount = 0;		// 최소 연산 횟수

		for (int i = 0; i < str.length(); i++) {
			if (str.charAt(i) == '{')
				stack.push(str.charAt(i));
			else {		// 닫는 괄호 '}'
				if (!stack.isEmpty())
					stack.pop();	// 매칭되는 여는 괄호 { 제거
				else {
					// 닫는 괄호 } 를 여는 괄호 { 로 변환하여 추가
					stack.push('{');
					minCount++;
				}
			}
		}

		minCount += (stack.size() / 2);
		return minCount;
	}

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

		int i = 1;
		while (true) {
			str = br.readLine();
			if (str.contains("-"))
				break;

			sb.append(i).append(". ")
				.append(solution(str)).append("\n");
			i++;
		}

		System.out.println(sb.toString());
	}
}