[백준] 1541번 잃어버린 괄호 - 문자열 파싱(Parsing) + Stack(스택) + 그리디(탐욕법, Greedy) JAVA

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

1541번: 잃어버린 괄호

코드설명

문자열 파싱(Parsing) + Stack(스택) + 그리디(탐욕법, Greedy)  를 활용합니다.

 

문제에서 핵심은 '-' 값을 만나면, 앞의 모든 숫자들을 다 더하기 처리해놓고 나가야 합니다.

이렇게 다 더하기 처리해놓고 나간다는 의미는 괄호를 씌운다는 의미입니다.

예를 들었을떄 55 - 50 + 40 이 들어왔다고 가정합니다.

이떄, 저는 원활한 처리를 위해 + 55 - 50 + 40 으로 맨 앞에 + 값을 붙여놓고 생각했습니다.

1. + 55 를 Stack에 넣습니다. { +, 55 }

2. - 50 에서 -를 만났으므로 Stack에서 { + , 55 } 를 빼서 +55 합니다. 이후에는 { - , 50 }을 다시 스택에 넣습니다.

3. + 40 을 만났으므로 { -, 50, + , 40 } 으로 스택이 변화됩니다.

4. 마지막이므로 Stack을 모두 Pop할 것 입니다. 이때, 총 계산값은 맨 앞의 Operand가 +냐 - 냐에 따라 달라집니다. - (50 + 40) 으로 - 90 을 빼줍니다.

 

 

두번쨰 방식은, 로직은 같지만 정규표현식을 활용해서 훨씬 더 간단하게 풀 수 있습니다.

입력으로 55-50+40+60 이 들어왔다고 가정합니다.

1. 처음에 먼저 "-" 로 split하여 {55} {50+40+60} 으로 나누어줍니다.

2. 그리고 각 {55}, {50+40+60}을 다시 "+"로 split합니다.

3. 만약 첫 연산(sum == Integer.MAX_VALUE)라면 해당 값을 더해줍니다.

4. 만약 첫 연산이 아니라면, '-' 값을 기준으로 split되었으므로 각 값들의 합을 모두 빼줍니다.

 

코드상에서의 추가적인 부분입니다.

str_split_by_subtraction_add = str_split_by_subtraction[i].split("\\+");
split의 경우 정규식(regex)을 받기때문에 "+"를 하면 regex.PatternSyntaxException을 받습니다.
문자가 메타문자(meta character)라 그렇습니다.(=특별한 의미를 담고있다는 뜻입니다.)
그렇기떄문에 온전하게 문자 그자체로 이용하기 위해서는 이스케이프 처리를 해야합니다.
하지만, \(백슬래시)도 단독으로 출력할 수 없기때문에 백슬래시 자체도 이스케이프해야합니다.
즉 \\+ 를 해야 우리가 분리하고자하는 "+"문자 그대로 분리할 수 있습니다.

 

 

예시로는, 
또한 예시로 55-50+40+60가 입력이 들어왔습니다.
 덧셈부분을 먼저 계산한뒤, 뺄셈부분을 계산하면 됩니다.
str_split_by_subtraction[0] = 55 , str_split_by_subtraction[1] = 50+40+60 으로 나뉩니다.
이제 더하기를 올바르게 수행하기 위해,
첫번쨰 반복문에서는,
str_split_by_subtraction_add[0] =55

두번째 반복문에서는
str_split_by_subtraction_add[0]=50
str_split_by_subtraction_add[1]=40 
str_split_by_subtraction_add[2]=60
으로 나뉘는데 이것을 모두 더한뒤, 
 -기준으로 나누었으므로 sum이 초기값이 아니라면, sum -=temp 값으로 해줍니다.

코드

import java.util.Scanner;

public class Main {
	
	public static String str = "";
	public static String str_split_by_subtraction[];
	public static String str_split_by_subtraction_add[];
	public static int temp=0;
	public static int sum = Integer.MAX_VALUE;
	public static void main(String[] args) {		
		Scanner sc = new Scanner(System.in);
		str = sc.nextLine();
		str_split_by_subtraction = str.split("-");
		
		for(int i=0;i<str_split_by_subtraction.length;i++) {
			temp=0;
			
			str_split_by_subtraction_add = str_split_by_subtraction[i].split("\\+");
			
			for(int j=0;j<str_split_by_subtraction_add.length;j++) {
				temp += Integer.parseInt(str_split_by_subtraction_add[j]);
			}
			
			if(sum == Integer.MAX_VALUE) {
				sum = temp;
			}else {
				sum -= temp;
			}
		}
		System.out.println(sum);
		
		
	}
	
}

 

Stack에 값을 넣어서 처리한 코드입니다.

'+' '숫자' 형식으로 2개씩 Stack에 넣은뒤, '-'를 계산합니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Stack;
import java.util.StringTokenizer;
 
public class Main {
	private static int N, K, M;
    private static int answer = 0;
    private static int[] arr;
    private static Stack<Integer> stack = new Stack<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        String str = st.nextToken();
        ArrayList<Integer> num = new ArrayList<>();
        ArrayList<Character> operand = new ArrayList<>();
        
        String[] split = str.split("[-,+]");
        for(String v : split) {
        	num.add(Integer.parseInt(v));
        }
        
        operand.add('+');
        for(int i=0;i<str.length();i++) {
        	if(str.charAt(i) == '-' || str.charAt(i) == '+') {
        		operand.add(str.charAt(i));
        	}
        }
        
        int numIdx = 0, operandIdx = 0;
        while(numIdx < num.size() && operandIdx < operand.size()) {
        	
        	//만약 '+'라면, stack에 연산자와 num을 차례로 넣습니다.
        	if(operand.get(operandIdx) == '+') {
        		stack.push(operand.get(operandIdx++) - '0');
        		stack.push(num.get(numIdx++));
        	}
        	
        	else if(operand.get(operandIdx) == '-') {
        		//기존 stack에 존재하는 것들 모두 pop하며 연산을 끝내놓습니다.
        		int totalValue = 0;
        		while(!stack.isEmpty()) {
        			//stack을 2개 뻅니다.
        			int numValue = stack.pop();
        			int operandType = stack.pop();
        			
        			//만약 '+' 타입이라면, totalValue값에 더해나갑니다.
        			if(operandType == '+' - '0') {
        				totalValue += numValue;
        			}
        			
        			//만약 음수라면, 기존의 totalValue를 - 값으로 바꾼뒤 더합니다.
        			if(operandType == '-' - '0') {
        				totalValue += numValue;
        				answer += (-totalValue);
        			}
        			
        			if(stack.isEmpty() && operandType == '+' - '0') {
        				answer += (totalValue);
        			}
        		}
        		
        		
        		stack.push(operand.get(operandIdx++) - '0');
        		stack.push(num.get(numIdx++));
        	}
        	
        }
        
        //마지막으로 남은 데이터들을 모두 연산합니다.
        //구조상, 마지막에는 '-'가 안나올 수 있기 때문입니다.
        int totalValue = 0;
		while(!stack.isEmpty()) {
			//stack을 2개 뻅니다.
			int numValue = stack.pop();
			int operandType = stack.pop();
			
			//만약 '+' 타입이라면, totalValue값에 더해나갑니다.
			if(operandType == '+' - '0') {
				totalValue += numValue;
			}
			
			//만약 음수라면, 기존의 totalValue를 - 값으로 바꾼뒤 더합니다.
			if(operandType == '-' - '0') {
				totalValue += numValue;
				answer += (-totalValue);
			}
			
			if(stack.isEmpty() && operandType == '+' - '0') {
				answer += (totalValue);
			}
		}
		
        
		System.out.println(answer);
        
    }
    
}