[Java] BOJ_1541. 잃어버린 괄호

🦍 문제

1541번: 잃어버린 괄호

---

🐈 문제 풀이

1. 무엇을 구해야 할까?

주어진 입력값을 토대로 괄호를 적절히 쳐 최소값의 결과를 만들어야 한다.

2. 어떻게 구해야 할까?

- 주어진 문자열에서 부호, 숫자를 적절히 파싱한다.

- 더하기, 빼기 연산만 있는 식에서 결과값을 최소화 하기 위해 어떤 부분에 괄호를 쳐야 할 지 고려해본다.

    -> 빼는 수를 크게 할 수록 결과값이 작아지므로 뺄셈 부호와 뺄셈 부호 사이의 식에 괄호를 쳐주면 된다.

    -> 이는 조금 더 나아가면 첫 뺄셈 부호를 만나기 이전의 값들은 모두 더하고, 그 이후의 값들은 모두 빼주면 된다는 결론에 도달한다.

 

- 문자열을 쭉 읽어나가며 부호를 만났을 때 부호 앞쪽 문자열을 Integer로 파싱

- 해당 숫자가 더해지는 숫자인지, 빼지는 숫자인지 판단 후 이에 맞는 ArrayList에 add

---

🐕‍🦺 소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String input = br.readLine();

		List<Integer> plus = new ArrayList<>();
		List<Integer> minus = new ArrayList<>();

		// start : 숫자 파싱에 사용할 인덱스 값
		int start = 0; 
        
		List<Integer> target = plus;
		for (int i = 1; i < input.length(); i++) {
        
        	// '+' 부호를 만났다면
			if (input.charAt(i) == '+') {
            
            	// 숫자를 파싱한 후 target 리스트에 저장
				target.add(Integer.parseInt(input.substring(start, i)));
				
                // start 인덱스 값 갱신
				start = i + 1;
			} 
            
            // '-' 부호를 만났다면
            else if (input.charAt(i) == '-') {
            
            	// 숫자를 파싱한 후 target 리스트에 저장
				target.add(Integer.parseInt(input.substring(start, i)));
				
                // start 인덱스 값 갱신
				start = i + 1;
                
                // 기존의 target 리스트가 plus였다면 minus로 변경
                // 이는 첫번째 '-' 부호를 만난 이후 다음의 값들은 모두 빼줘야 한다는 결론과 부합
				if (target == plus) {
					target = minus;
				}
			}
		}
        
        // 가장 뒤에 위치한 숫자를 target 리스트에 저장
		target.add(Integer.parseInt(input.substring(start, input.length())));

		int answer = 0;
		for (int i : plus) {
			answer += i;
		}
		for (int i : minus) {
			answer -= i;
		}

		System.out.print(answer);

	}
}

---

---

🐖 Think

 - 그리디 알고리즘 문제는 거의 풀어본 적 없어 사실 접근이 쉽지는 않았다.

 - 정답을 도출하기 위한 조건들을 나열한 후, 각 조건에 부합되도록 코드를 작성하는 연습을 해봐야겠다.