https://www.acmicpc.net/problem/9012
코드설명
스택 자료구조 문제입니다.
문제로직입니다.
- '(' 가 들어올시 Stack에 일단 넣습니다.
- ')'가 들어올시
- Stack이 비어있다면, ')' 가 먼저 들어왔다는 의미로 벌써 실패한 괄호이므로 "NO"를 출력시키고 중단시킵니다.
- Stack에 값이있다면, '(' 가 맨위에 있을때만 스택에서 pop 시킵니다. 이유는 ')'가 들어올떄마다 '('를 무조건 1번 빼므로 반드시 '(' 가 있어야만합니다.
코드
함수를 사용하여 손쉽게 처리
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Stack;
import java.util.StringTokenizer;
public class Main {
public static int N;
public static Stack<Character> stack = new Stack<>();
public static boolean flag = false;
public static int answer = 0;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
for(int i=0;i<N;i++) {
st = new StringTokenizer(br.readLine());
stack.clear();
char[] ch= st.nextToken().toCharArray();
simulate(ch);
}
}
public static void simulate(char[] ch) {
for(int j=0;j<ch.length;j++) {
if(ch[j] == '(') {
stack.add('(');
}else if(ch[j] == ')') {
if(stack.isEmpty()) { // ')'가 들어왔을때 아무것도 없다면, 잘못된 괄호이므로 중단시킵니다.
System.out.println("NO");
return ;
}
if(stack.peek() == '(') { // ')' 가 들어왔을때 stack의 맨위 값이 '(' 라면
char popWords = stack.pop(); // 뽑고서 break.
}
}
}
if(stack.isEmpty()) {
System.out.println("YES");
}else {
System.out.println("NO");
}
}
}
함수를 사용하지않고 내부에 사용하여서 flag가 조금 복잡합니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Stack;
import java.util.StringTokenizer;
public class Main {
public static int N;
public static Stack<Character> stack = new Stack<>();
public static boolean flag = false;
public static int answer = 0;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
for(int i=0;i<N;i++) {
st = new StringTokenizer(br.readLine());
stack.clear();
flag = false;
char[] ch= st.nextToken().toCharArray();
for(int j=0;j<ch.length;j++) {
if(ch[j] == '(') {
stack.add('(');
}else if(ch[j] == ')') {
if(stack.isEmpty()) { // ')'가 들어왔을때 아무것도 없다면, 잘못된 괄호이므로 중단시킵니다.
flag = true;
break;
}
while(!stack.isEmpty()) { // ')' 가 들어왔을때 값이 존재한다면,
if(stack.peek() == '(') { // ')' 가 들어왔을때 stack의 맨위 값이 '(' 라면
char popWords = stack.pop(); // 뽑고서 break.
break;
}
else {
flag = true;
break;
}
}
}
}
if(!stack.isEmpty() || flag == true) {
System.out.println("NO");
}
else if(stack.isEmpty()) {
System.out.println("YES");
}
}
}
public static void printstack() {
for(int a : stack) {
System.out.print(" "+ a);
}
}
}
'알고리즘 > 백준' 카테고리의 다른 글
[백준] 1158 요세푸스 문제 - 큐 + 자료구조 JAVA (0) | 2023.09.02 |
---|---|
[백준] 18258 큐 2 - 큐 + 자료구조 JAVA (0) | 2023.09.02 |
[백준] 10828 스택 - 스택 + 자료구조 JAVA (0) | 2023.09.02 |
[백준] 12851 숨바꼭질 2 - BFS JAVA (0) | 2023.09.01 |
[백준] 17070 파이프 옮기기 1 - DP + DFS + BFS JAVA (0) | 2023.09.01 |