2504 : 괄호의 값 ( 백준 / java )

 

 

*해결 과정

 

 괄호를 가지고 계산하는 것은 보통 stack을 이용하면 됩니다. 이 문제도 마찬가지로 stack을 이용합니다. 이전의 stack문제와 다른 것은, '(' 에 대한 ')'의 위치 index를 저장하고 재귀적으로 해결했지만 이번에는 그런 방식으로 하면 시간초과가 난다는 것입니다. 그래서 문자열을 하나씩 탐색하면서 Nlog(N)에 해결하도록 하였습니다. (N은 문자열 길이이고, 문자열을 하나씩 살펴보며 검사하지만 괄호 안에 다른 내용이 있을 경우 다시 while문 으로 모두 stack.pop()하는 과정이 있으므로 최악의 경우 N을 곱했습니다.) 특히 '('는 0으로 치환, '['은 1로 치환하여 stack에 저장하였으며 어차피 계산과정에서 0과 1을 만날 일이 없기 때문에 괄호라고 식별 가능합니다.

 

제한 사항 확인!

 제한 사항때문에 복잡해진 문제였습니다. '(' ']'의 짝의 갯수가 맞는 것은 물론 왼쪽 괄호가 먼저 나오고 오른쪽 괄호가 나중에 나와야 하는 조건도 만족시켜야 했습니다. 따라서 '(' ']' 2가지의 경우에 변수를 만들어 계속 1씩 더하기를 했고 ')' ']'에 맞춰 계속 1씩 빼주었습니다. 시물레이션처럼 case를 나누어서 풀었으며, 괄호 안에 다른 숫자들이 올 수 있는 경우에는 별도로 함수로 재귀를 하지 않고 while문을 사용하여 안에서 계산하도록 하였습니다. whlie을 통해 반대쪽 괄호를 찾기 위해 stack.pop()을 하는데 stack의 값이 0보다 작은 경우에는 0을 출력하도록 했습니다.

 

*1번 해결과정 ( 시간초과  - 많은 재귀의 시간 )

package bj;

import java.util.*;
public class Main {

	static String line = "";
	
	static Stack<Integer> stack1 = new Stack<>();
	static Stack<Integer> stack2 = new Stack<>();
	static int[] reverse1;
	static int[] reverse2;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		line = sc.nextLine();
		
		reverse1 = new int[31];
		reverse2 = new int[31];
		
		for(int i=0;i<line.length();i++) {
			if(line.charAt(i)=='(') stack1.add(i);
			if(line.charAt(i)=='[') stack2.add(i);
			
			if(line.charAt(i)==')') {
				if(stack1.size()==0) {
					System.out.println(0);
					return;
				}
				reverse1[stack1.pop()] = i;
			}
			if(line.charAt(i)==']') {
				if(stack2.size()==0) {
					System.out.println(0);
					return;
				}
				reverse2[stack2.pop()] = i;
			}
		}
		System.out.println(traversal(0,line.length()));
	}
	
	public static int traversal(int start, int end) {
		int val = 1;
		for(int i=start;i<end;i++) {
			if(line.charAt(i)=='(') {
				val += 2 * traversal(i+1, reverse1[i]);
				i=reverse1[i];
			}
			
			if(line.charAt(i)=='[') {
				val += 3 * traversal(i+1, reverse2[i]);
				i=reverse2[i];
			}
		}
		if(val!=1) return val-1;
		return val;
	}
}

 

 

*2번 해결과정 

package bj;

import java.util.*;
public class Main {

	static String line;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		line = sc.nextLine();
		
		int sum=0;
		Stack<Integer> stack = new Stack<>();
		int zeroCnt=0;
		int oneCnt=0;
		
		for(int i=0;i<line.length();i++) {
			
			char c = line.charAt(i);
			if(c=='(') {
				stack.add(0);
				zeroCnt++;
			}
			if(c=='[') {
				stack.add(1);
				oneCnt++;
			}
			
			if(c==')') {
				if(zeroCnt==0) {
					System.out.println("0");
					return;
				}
				if(stack.peek()==0) {
					stack.pop();
					stack.add(2);
				} else {
					int temp=0;
					while(stack.peek()!=0) {
						temp += stack.pop();
						if(stack.size()==0) {
							System.out.println("0");
							return;
						}
					}
					stack.pop();
					temp = temp*2;
					stack.add(temp);
				}
				zeroCnt--;
			}
			
			if(c==']') {
				if(oneCnt==0) {
					System.out.println("0");
					return;
				}
				if(stack.peek()==1) {
					stack.pop();
					stack.add(3);
				} else {
					int temp=0;
					while(stack.peek()!=1) {
						temp += stack.pop();
						if(stack.size()==0) {
							System.out.println("0");
							return;
						}
					}
					stack.pop();
					temp = temp*3;
					stack.add(temp);
				}
				oneCnt--;
			}
		}
		
		if(oneCnt!=0 || zeroCnt!=0) {
			System.out.println("0");
			return;
		}
		
		for(int val : stack)
			sum += val;
		System.out.println(sum);
	}
}