[알고리즘] 백준 4889 안정적인 문자열 Java

문제 정보

플랫폼 : 백준
분류 : 그리디 알고리즘, 스택
난이도 : 실버1
링크 : https://www.acmicpc.net/problem/13305

입력 데이터와 시간제한 검증

입력 데이터 갯수 : 알 수 없음 (BufferedReader 사용)
O(n) 풀이 : 시간제한 ok

풀이

괄호 문제가 나오면 일단 스택을 생각해야한다!

1. Input TestCase가 몇개인지 모르므로 while문으로 입력을 받는다. '-'문자가 있을경우 while문을 종료.
2. 문자열의 첫 번째 글자부터 순회한다.
   2-1. 만약 문자가 '{' 라면, 그대로 스택에 담는다.
   2-2. 만약 문자가 '}'라면, 현재 스택을 확인한다.
   2-2-1. 스택이 비어있다면, 문자를 '{'로 변경하여 스택에 저장하고, 변경 횟수를 1 늘린다.
   2-2-2. 스택이 비어있지 않다면 ('{'가 들어있는 경우) 스택을 pop한다.
3. 2-2-1에서 늘린 변경횟수 + 스택사이즈/2 만큼을 출력한다.

스택사이즈/2 이유 : 스택에는 '{'문자만 들어가있다. '}'가 오면, pop하기 때문이다. 만약 스택에 ['{', '{']가 들어있다면, 2번째 하나만 '}'로 변경하면 되므로, /2를 해주는 것이다.

코드

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));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int no = 1;
		//1. Input TestCase가 몇개인지 모르므로 while문으로 입력을 받는다.
		while(true) {
			String str = br.readLine();
			if(str.contains("-")) break; // '-'가 포함돼있으면 while문 종료
			
			int n = str.length();
			int cnt = 0;
			Stack<Character> st = new Stack<>();
			
			//2. 문자열의 첫 번째 글자부터 순회한다.!
			for(int i = 0; i < n; i++) {
				char tmp = str.charAt(i);
				if(tmp == '{') {
					//2-1. 만약 문자가 '{' 라면, 그대로 스택에 담는다.
					st.add(tmp);
				}else {
					//2-2. 만약 문자가 '}'라면, 현재 스택을 확인한다.
					if(st.isEmpty()) {
						//2-2-1. 스택이 비어있다면, 문자를 '{'로 변경하여 스택에 저장하고, 변경 횟수를 1 늘린다.
						cnt++;
						st.add('{');
					}
					else
						//2-2-2. 스택이 비어있지 않다면 ('{'가 들어있는 경우) 스택을 pop한다.
						st.pop();
				}
			}
			//3. 2-2-1에서 늘린 변경횟수 + 스택사이즈/2 만큼을 출력한다.
			bw.write((no++) + ". " + (cnt + st.size()/2) + "\n");
		}
		br.close();
		bw.flush();
		bw.close();
	}
}

더 많은 정답 코드

블로그를 쓰기 이전에 풀어본 문제들이 많다. 해설강의는 없지만, 백준 문제의 풀이 코드가 필요한 경우 이곳을 클릭하여 소스코드를 참조해보도록 하자. 단, 코드만 복사-붙여넣기 하는것은 본인에게 결코 도움이 되지 않는다. 반드시 먼저 생각해보고, 막히는 경우에 참고하고 왜 이렇게 코드가 작성됐는지를 다시 한 번 생각해보는 습관을 들이자.