다희의 코딩 성장일기
[백준] 4889. 안정적인 문자열(자바 JAVA) 본문
[ 문제 ] [백준] 4889. 안정적인 문자열(자바 JAVA)
문제 링크 : https://www.acmicpc.net/problem/4889
# 접근 방법 및 풀이
- 스택을 이용해서 풀었다.
- 문제에서 연산은 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
'Algorithm > 백준 BOJ' 카테고리의 다른 글
[백준] 2583. 영역 구하기 (자바 JAVA) (0) | 2021.08.21 |
---|---|
[백준] 1726. 로봇 (자바 JAVA) (0) | 2021.08.19 |
[백준] 17141. 연구소2 (자바 JAVA) (0) | 2021.08.17 |
[백준] 14719. 빗물 (자바 JAVA) (0) | 2021.08.17 |
[백준] 2504. 괄호의 값 (자바 JAVA) (2) | 2021.08.16 |
Comments