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

문제 출처 - Baekjoon Online Judge

문제는 여기

4889번: 안정적인 문자열

[문제] 

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

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

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

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

[입력]

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

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

[출력]

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

 

 

---

[풀이]

1. 여는 괄호가 나온다면 스택에 담아준다.

2. 닫는 괄호가 나온다면 스택을 체크한다.

3. 스택에 여는 괄호가 있다면 스택에서 하나를 빼준다.

4. 스택에 여는 괄호가 없다면 닫는 괄호를 여는 괄호로 바꾸는 과정이 필요하므로 횟수를 1회 증가시키고 스택에 여는 괄호를 넣어준다.

5. 2~4번을 문자열의 길이만큼 반복한다.

6. 다 하고 남아있는 스택의 사이즈에서 반을 닫는 괄호로 바꿔주면 안정적인 문자열로 만들 수 있으므로 스택의 사이즈의 반을 횟수에 더해준다.

7. 이후, 횟수를 출력해준다.

[접근]

1. 여는 괄호('{')의 경우라면 매칭되는 닫는 괄호('}')의 개수를 구해 서로 제거해준다.

2. 남은 여는 괄호의 개수의 반을 닫는 괄호로 변경해주면 된다.

[코드]

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

public class Main {
	static int t = 1;

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

		while(true) {
			String str = br.readLine();
			
			// -가 포함되면 연산 종료
			if (str.contains("-"))
				break; 
			
			int n = str.length();
			int cnt = 0;
			Stack<Character> st = new Stack<>();
			
			for (int i = 0; i < n; i++) {
				char c = str.charAt(i);
				
				// 만약, 여는 괄호라면
				if (c == '{') {
					st.add(c); // 그대로 스택에 추가
				}
				else { // 닫는 괄호라면
					// 스택이 비어있는지를 체크
					if (st.isEmpty()) { // 스택이 비어있다면
						st.add('{'); // 여는 괄호를 스택에 추가
						cnt++; // } > {로 변경했으므로 변경 횟수 추가
					}
					// 스택이 비어있지 않다면
					else
						// 스택에서 { 하나를 빼냄
						st.pop();
				}
			}
			// 스택에 남아있는 { 개수를 구해준다.
			int left = st.size();
			// 남아있는 갯수의 반을 }로 변경해주면 안정적인 문자열이 된다.
			cnt += (left / 2);
			
			System.out.println(t + ". " + cnt);
			t++;
		}
	}
}