[백준] [4889] 안정적인 문자열 (stack) (JAVA)

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

4889번: 안정적인 문자열

---

문제

여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어진다. 여기서 안정적인 문자열을 만들기 위한 최소 연산의 수를 구하려고 한다. 안정적인 문자열의 정의란 다음과 같다.

1. 빈 문자열은 안정적이다.
2. S가 안정적이라면, {S}도 안정적인 문자열이다.
3. S와 T가 안정적이라면, ST(두 문자열의 연결)도 안정적이다.

{}, {}{}, {{}{}}는 안정적인 문자열이지만, }{, {{}{, {}{는 안정적인 문자열이 아니다.

문자열에 행할 수 있는 연산은 여는 괄호를 닫는 괄호로 바꾸거나, 닫는 괄호를 여는 괄호로 바꾸는 것 2가지이다.

입력

입력은 여러 개의 데이터 세트로 이루어져 있다. 각 데이터 세트는 한 줄로 이루어져 있다. 줄에는 여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어진다. 문자열의 길이가 2000을 넘는 경우는 없고, 항상 길이는 짝수이다.

입력의 마지막 줄은 '-'가 한 개 이상 주어진다.

출력

각 테스트 케이스에 대해서, 테스트 케이스 번호와 입력으로 주어진 문자열을 안정적으로 바꾸는데 필요한 최소 연산의 수를 출력한다.

예제 입력 1 복사

}{
{}{}{}
{{{}
---

예제 출력 1 복사

1. 2
2. 0
3. 1

---

※ JAVA 코드 (안정적인 문자열)

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Stack<Character> s = new Stack<>();
		int idx = 1;
		
		while(true) {
			s.clear();
			int openCnt = 0;
			int closeCnt = 0;
			String input = br.readLine();
			if(input.indexOf("-") > -1) {
				break;
			}
			
			for(int i = 0; i < input.length(); i++) {
				if(s.size() > 0 && s.peek() != null && (s.peek() == '{' && input.charAt(i) == '}')) {
					s.pop();
				} else {
					s.add(input.charAt(i));
				}
			}
			
			while(!s.isEmpty()) {
				char c = s.pop();
				
				if(c == '{') {
					openCnt++;
				} else {
					closeCnt++;
				}
			}
			int dap = 0;
			dap = openCnt % 2 == 0 ? openCnt / 2 : openCnt / 2 + 1;
			dap += closeCnt % 2 == 0 ? closeCnt / 2 : closeCnt / 2 + 1;
			
			System.out.println(idx + ". " + dap);
			idx++;
		}
	}
}

---

※ 생각정리 (안정적인 문자열)

안정적인 문자열 문제는 스택을 이용하면 꽤 쉽게 풀 수 있는 문제였다.

먼저, 무한루프를 돌면서 입력받는 문자열에 '-'가 한개라도 포함되어있다면 반복문을 빠져나간다.

'{' 또는 '}'가 입력되었을 때 스택의 가장 윗 문자가 '{' 이고 현재 들어오는 문자가 '}' 이라면 stack.pop()을 통해 값을 빼낸다.

최종적으로 스택에 남은 문자들 중에서 '{'와 '}'의 개수를 각각 세고 해당 문자의 개수가 짝수일때와 홀수일때를 나누어 값을 담는다.

-새벽코딩-