[백준 / Java] 1541번: 잃어버린 괄호 (실버2)

문제 풀이 날짜: 2023.05.22
포스트 작성일: 2023.05.23

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

백준 온라인 저지 1541번: 잃어버린 괄호 (실버2) (문제 링크)

 

키워드

그리디

 

풀이 접근법

• 식에 괄호를 여러 개 칠 수 있고, 하나의 괄호 안에 여러 개의 수가 들어갈 수 있다.
• (양수 + 어떤 수) 조합은 괄호를 쳐도 별 일이 일어나지 않는다.
• (음수 + 어떤 수) 조합에 괄호를 칠 때 주의가 필요하다.
  • 괄호 안의 수는 모두 부호가 반대가 된다.
  • 따라서 현재 가리키는 수가 양수라면 그냥 결과에 더해주고, 음수라면 적절한 연산을 한다.
  1. 괄호를 쳐야 하는 경우 : 뒤에 이어지는 수도 양수일 때
  2. 괄호를 치지 않아야 하는 경우 : 뒤에 이어지는 수가 음수일 때 (결괏값이 더 커진다)
• 반복문을 돌다가 음수를 만났다면… 
  • 음수를 만났을 때, 다음 수로 또 음수가 나올 때까지 양수들과 함께 괄호를 친다.
  • 즉, 다음에 나오는 양수들은 무조건 부호를 뒤집어서 더해준다.
• 입력 String의 첫 번째 수부터 음수일 수도 있으니 처리에 주의하자.

 

코드

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String formula = br.readLine();
		
		ArrayList<Integer> numbers = new ArrayList<>();
		ArrayList<Character> operators = new ArrayList<>();
		
		StringTokenizer st = new StringTokenizer(formula, "+-");
		while(st.hasMoreTokens()) {
			numbers.add(Integer.parseInt(st.nextToken()));
		}
		
		for(int i = 0; i < formula.length(); i++) {
			char c = formula.charAt(i);
			if(c == '+' || c == '-') {
				operators.add(c);
			}
		}
		
		int result = 0;
		int numIdx = 0;
		int opeIdx = 0;

		//첫 번째로 더하는 수가 양수라면
		if(numbers.size() != operators.size()) {
			result += numbers.get(0);
			numIdx = 1; //처리해주고 인덱스를 하나 증가시킨다.
		}

		int multiplier = 1;
		while(numIdx < numbers.size() || opeIdx < operators.size()) {			
			if(operators.get(opeIdx) == '-') { //음수를 만났다면
				multiplier = -1; //이 뒤로 괄호를 쳐서 음수로 만든다.
			}
			
			result += (numbers.get(numIdx) * multiplier);
			
			numIdx++;
			opeIdx++;
		}
		
		System.out.print(result);
	}

}

---

괄호의 특성을 이용하면 어렵지 않게 풀 수 있는 그리디 문제이다. 만약 정말로 문자열 사이사이에 괄호를 치려고 하면 조금 위험해진다. (과거의 나라면 그렇게 풀었을 듯하다.) 적당한 덧셈 뺄셈으로만 해결이 가능하다.

 

git 링크

https://github.com/jinju9553/23-CodingTest/blob/main/week9/day1/Q1541.java