다희의 코딩 성장일기

[백준] 4889. 안정적인 문자열(자바 JAVA) 본문

Algorithm/백준 BOJ

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

ilmiodiario 2021. 8. 18. 23:25

[ 문제 ]  [백준] 4889. 안정적인 문자열(자바 JAVA)

 

문제 링크 : https://www.acmicpc.net/problem/4889

 

4889번: 안정적인 문자열

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

www.acmicpc.net

 

 

 


# 접근 방법 및 풀이 

 

  • 스택을 이용해서 풀었다.
  • 문제에서 연산은 2가지. "여는 괄호 -> 닫는괄호" or "닫는괄호 -> 여는괄호"
  • '{' 여는 괄호라면 스택에 넣어주고, 닫는 괄호라면 스택에 들어있는 여는괄호를 뽑는다.
  • 근데 이때 여는 괄호가 들어있지 않다면, 닫는 괄호를 여는 괄호로 만들어서 스택에 넣어준다.
  • 그래서 입력이 }{ 로 들어왔다면, {{ 로 들어있을 것이다.
  • 그렇게 입력받은 문자열을 다 돌고 스택이 비어있다면 올바른 괄호열이었을 것이고, 스택에 괄호가 남아있다면 여는 괄호열을 닫는 괄호열로 변경하는 연산을 해야한다.
  • 입력은 짝수개가 들어오기때문에 남아있는 스택 size()/2를 해서 닫는 괄호열로 바꾸는 연산수를 더해주면 된다.
  • {{{{ 가 스택에 들어있다면 이중 두개의 여는 괄호열을 닫는 괄호열로 바꿔주면 되기 때문이다.

# 주의할 점 

 

  • 조오금 생각해볼 문제였다! 스택을 이용한 괄호문제를 많이 풀어봤다면 쉽게 풀어볼 수 있다,

 

JAVA 코드
package Silver;

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

public class bj4889_안정적인문자열 {

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int tc = 1;
		while(true) {
			String s = in.readLine();
			if(s.contains("-"))
				break;
			char arr[] = s.toCharArray();
			int cnt = 0;
			Stack<Character> stack = new Stack<Character>();
			for (int i = 0; i < arr.length; i++) {
				char c = arr[i];
				if(c == '{') {
					stack.add(c);
				}else {
					if(stack.isEmpty()) {
						cnt++;
						stack.add('{');
						continue;
					}else {
						stack.pop();
					}
				}
			}
			if(!stack.isEmpty()) {
				cnt += stack.size()/2;
			}
			System.out.println(tc+". "+cnt);
			tc++;
		}
		
	}
}

 

 

REVIEW

Comments