https://www.acmicpc.net/problem/9012

 

9012번: 괄호

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고

www.acmicpc.net

코드설명

스택 자료구조 문제입니다.

 

문제로직입니다.

  1. '(' 가 들어올시 Stack에 일단 넣습니다.
  2. ')'가 들어올시
    1. Stack이 비어있다면, ')' 가 먼저 들어왔다는 의미로 벌써 실패한 괄호이므로 "NO"를 출력시키고 중단시킵니다.
    2. 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);
    	}
    }
    
    
    
}

+ Recent posts