1. 주요 아이디어
닫는 괄호가 나올 시 직전 괄호가 여는 것인지, 닫는 것인지 확인하여 막대기 조각의 갯수를 구하자
1.1. 여는 괄호가 나올 시
push()
1.2. 닫는 괄호가 나올 시
pop()
단, 이때 직전 괄호가
- 1) 여는 괄호라면 이는 곧 레이저를 지나가는 막대기의 수(스택의 사이즈)만큼의 조각이 생기는 것 이기에 result + 스택의 사이즈.
- 2) 닫는 괄호라면 한 개의 막대기가 끝나는 지점이기에 result + 1.
2. 풀이
package BOJ.dataStructure.stack;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
public class BOJ10799 {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 괄호들을 입력받을 변수 생성
String brackets = br.readLine();
br.close();
// 괄호를 넣어줄 스택 생성
Stack<Character> stack = new Stack<>();
// Deque<Character> deque = new ArrayDeque<>();
// 조각의 갯수를 넣어줄 변수 생성
int result = 0;
for(int i = 0; i < brackets.length(); i++) {
// 여는 괄호가 나올 시
if(brackets.charAt(i) == '(') {
stack.push('(');
// 닫는 괄호일 시
} else {
stack.pop();
// 직전 괄호가 여는 괄호일 시
if(brackets.charAt(i-1) == '(') result += stack.size();
// 직전 괄호가 닫는 괄호일 시
else result++;
}
}
System.out.println(result);
}
}
'코딩테스트 > Java' 카테고리의 다른 글
[BaekJoon][자료 구조][Queue][Java] 큐 구현하기 (0) | 2024.08.10 |
---|---|
[BaekJoon][자료 구조][Stack][Java] 2563: 색종이 (0) | 2024.08.10 |
[BaekJoon][자료 구조][Stack][Java] 1935 : 후위 표기식2 (0) | 2024.08.10 |
[BaekJoon][자료 구조][Stack][Java] 10773 : 제로 (0) | 2024.08.10 |
[BaekJoon][자료구조][Java] Stack 구현하기 (0) | 2024.08.10 |