[Java+Python]1541번, 잃어버린 괄호

목차

 

 

Greedy Algorithm

 

[Java+Python]11047번, 동전 0

[Java+Python]1931번, 회의실 배정

[Java+Python]11339번, ATM

[Java+Python]13305번, 주유소

 

문제

 

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다.

 

그리고 나서 세준이는 괄호를 모두 지웠다.

그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.

괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

 

입력

 

첫째 줄에 식이 주어진다. 

 

식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 

 

그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 

 

수는 0으로 시작할 수 있다. 

 

입력으로 주어지는 식의 길이는 50보다 작거나 같다.

 

출력

 

첫째 줄에 정답을 출력한다.

 

풀이

 

주어진 식에 괄호를 추가해서 합이 최소가 되려면, 덧셈 기호(+)로 연결된 모든 숫자를 더하고 마지막에 뺄셈 연산을 하면 된다.

 

이를 이해했다면 조금 간단하게 처리하기 위해 처음 뺄셈 기호(-)를 만나기 전까지만 숫자를 더해주고

 

그다음부터는 계속해서 빼주면 된다.

 

각 변수를 포함한 알고리즘의 흐름은 다음과 같다.

 

1. 주어진 식을 통째로 문자열로 입력받아 expression에 저장한다.
2. 최종 결과를 저장할 변수 total을 0으로 초기화한다.
3. 중간 연산을 저장할 변수 subTotal을 0으로 초기화한다.
   1. 중간 연산이라고 적어서 헷갈릴 수 있겠지만 해당 문자가 연산자가 아닌 경우 숫자를 구성하는데 쓰인다.
   2. 이를 표현한 부분이 자바 코드의 subTotal = subTotal * 10 + (ch - '0'); 이다.
4. 문자열을 순회하며 첫 뺄셈이 나온 이후의 값은 모두 뺄셈으로 바꿔준다.
5. 반복문이 끝난 뒤 마지막 숫자를 같은 방식으로 빼준다.

코드만 읽으면 더하고 빼고를 반복하는 듯 보일 수 있지만 덧셈은 첫 뺄셈 기호 이후엔

 

다시 기호를 만나기 전의 숫자 구성에만 쓰인다.

 

Java

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Prob1541 {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String expression = br.readLine();

		int total = 0;
		int subTotal = 0;
		boolean isSubtract = false;

		for (int i = 0; i < expression.length(); i++) {

			char ch = expression.charAt(i);

			if (ch == '+' || ch == '-') {

				total += isSubtract ? -subTotal : subTotal;
				subTotal = 0;

				if (ch == '-') {
					isSubtract = true;
				}
			} else {
				subTotal = subTotal * 10 + (ch - '0');
			}
		}

		total += isSubtract ? -subTotal : subTotal;

		System.out.println(total);
	}
}

 

Python

 

import sys

expression = sys.stdin.readline().rstrip()

total = 0
sub_total = 0
is_subtract = False

for i, ch in enumerate(expression):
    if ch == '+' or ch == '-':
        total += -sub_total if is_subtract else sub_total
        sub_total = 0

        if ch == '-':
            is_subtract = True

    else:
        sub_total = sub_total * 10 + int(ch)

total += -sub_total if is_subtract else sub_total

print(total)

VSCode의 추천대로 enumerate() 내장함수를 이용해서 풀어보았다.

 

Performance