Algorithm/백준 알고리즘
백준_4889 안정적인 문자열(자바) / 자료구조 , 문자열
미스터로즈
2021. 9. 9. 09:27
시간&메모리 제한
문제
입력&출력
문제풀이
package com.Back;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
public class Back_4889 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
String tmp;
int n = 1;
while(true) {
tmp = br.readLine();
if(tmp.charAt(0)=='-') break;
int ans =0;
Stack<Character> st = new Stack<>();
for (int i = 0; i < tmp.length(); i++) {
char c = tmp.charAt(i);
if(c=='{') {
st.add(c);
}else {
if(st.isEmpty()) {
ans++;
st.add('{');
}else {
st.pop();
}
}
}
sb.append((n++) +". " + (ans+st.size()/2)+"\n" );
}
System.out.println(sb);
}
}
※ 내 생각
이 문제는 자료구조의 스택을 이용하여 해결하는 문제입니다.
먼저 이 문제를 해결하기 위해서 while을 만들어 주고, 값을 받습니다.
받아온 값의 길이 만큼 for문을 돌려줍니다.
for문에서는 { 의 문자열의 경우 추가시켜줍니다.
} 의 문자열인 경우 비어 있으면 ans 의 값을 증가시켜줍니다.
비어 있지 않다면 { 의 문자열을 빼줍니다.
마지막에 값을 계산할 때는 ans에 스택에 남아있는 { 의 값의 절반은 } 로 바꿔줘야 하므로 크기의 절반을 더해줍니다.