스택과 괄호의 값

문제 : https://www.acmicpc.net/problem/2504

1. 개요

주어진 괄호들이 규칙에 맞는지 확인, 계산하는 문제입니다.

2. 고난과 역경

1) check ()

우선 괄호의 짝이 맞는지 확인하기 위해 왼쪽 괄호를 하나씩 읽어와 스택에 추가합니다.

오른쪽 괄호를 만났을 때 스택이 비어있거나, 꺼내온 값이 왼쪽 괄호가 아니라면 규칙에 어긋나므로 0을 리턴합니다.

처음 완성한 check() 에는 " ( ( [ " 와 같이 왼쪽 괄호만이 들어왔을 때 그냥 통과시켜버리는 문제가 있었습니다.

check가 규칙에 맞지 않는 녀석들을 통과시켜버리는 바람에  EmptyStackException  이 발생했습니다.

for 문이 종료되었을 때, 스택에 값이 남아있다면 0을 리턴하는 문장을 추가하여 문제를 해결했습니다.

2) 계산

괄호만으로 이루어진 문자열에서 계산을 하려면 숫자가 필요합니다.

가장 안쪽에 있는 괄호를 숫자로 바꾸는 것부터 구현을 했습니다.

( ( ) [ ] ( ( ) ) ) 의 경우는 ( 2 3 ( 2 ) ) 로 바뀝니다.

그다음 스택에 숫자도 같이 넣었다가 꺼내면서  op  괄호 사이에 있는 숫자는 모두 더해주고 그 값에 2 또는 3을 곱해주기로 했습니다.

3. 구현

import java.util.*;

class Main {
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	String s = sc.nextLine();
    	Stack<String> stk = new Stack<String>();
    	
    	int[] counter = {0, 0};
    	int result = 0;
    	
    	if(check(stk, s)==0) System.out.println(0);
    	else {
    		stk.empty();
	    	for(int i = 0; i < s.length(); i++) {
	    		if(!stk.isEmpty()&& s.charAt(i)==')'&& stk.pop().equals("(")) {
    				if(s.charAt(i-1)=='(') { 
    					s = s.substring(0, i-1) + "2" + s.substring(i+1);
    					i--;
    				}
	    		}
	    		else if(!stk.isEmpty()&& s.charAt(i)==']' && stk.pop().equals("[")) {
	    			if(s.charAt(i-1)=='[') {
	    				s = s.substring(0, i-1) + "3" + s.substring(i+1);
	    				i--;
	    			}
	    		}
	    		else stk.push(s.substring(i,i+1));
	    	} 
	    
	    	stk.empty();
	    	int op=0;
	    	String c="";
    	
	    	for(int i = 0; i < s.length(); i++) {
	    		if(!stk.isEmpty()&&s.charAt(i)==')') {
	    			do {
	    				c = stk.pop();
	    				if(!c.equals("(")) op+=Integer.parseInt(c);
	    			} while(!c.equals("("));
	    			op*=2;
	    			stk.push(Integer.toString(op));
	    			op=0;
	    		}
	    		else if(!stk.isEmpty()&&s.charAt(i)==']') {
	    			do {
	    				c = stk.pop();
	    				if(!c.equals("[")) op+=Integer.parseInt(c);
	    			} while(!c.equals("["));
	    			op*=3;
	    			stk.push(Integer.toString(op));
	    			op=0;
	    		}
	    		else stk.push(s.substring(i,i+1));
	    	}
	    	op=0;
	    	while(!stk.isEmpty()) op+=Integer.parseInt(stk.pop());
	    	System.out.println(op);
	    	}
    	
    }
    	
    public static int check(Stack<String> stk, String s) {
    	for(int i = 0; i < s.length(); i++) {
    		if(s.charAt(i)==')') {
    			if(stk.isEmpty()) return 0;
    			if(!stk.pop().equals("(")) return 0;  
    		}
    		else if(s.charAt(i)==']') {
    			if(stk.isEmpty()) return 0;
    			if(!stk.pop().equals("[")) return 0;
    		}
    		else stk.push(s.substring(i,i+1));
    	}
    	if(!stk.isEmpty()) return 0;
    	return 1;
    }
}

 

4. 반성과 참회

굳이 스택을 쓰지 않아도 괄호의 개수를 세는 것만으로 짝이 맞는지 확인할 수 있습니다.

굳이 숫자를 집어넣을 필요 없이 1에서 시작해서 매번 어떤 괄호가 나오는지에 따라 곱하기 더하기를 해주는 것만으로도 풀리는 문제였습니다.

오늘도 간단한 것을 복잡하게 풀었구나 하는 생각이 듭니다.