문제

BOJ 1541, 잃어버린 괄호

핵심

• 입력의 크기가 $50$이라 구현에 초점을 맞춘다.
• 양수, +, -로 이루어진 식이 주어진다. 괄호를 적절히 사용해서 식을 최솟값으로 만들려고 할 때 해당 최솟값을 구해야 한다.
• 음수 연산자가 나오면 괄호를 이용해 뒤에 +연산자가 있든 간에 상관없이 음수로 만들 수 있다. 예를 들어 [- 5 + 2 + 3 + 4 + 7]의 경우 -21로 만들 수 있다. 중간에 음수 연산자가 나오더라도 음수 연산자 전까지만 괄호로 묶으면 되므로 문제가 되지 않는다. - 연산자부터는 모든 + 연산자를 괄호로 묶으면 가장 큰 음수가 되어 최솟값이 되는 그리디 풀이이다. 괄호 제한이 없기 때문에 간단히 구현할 수 있다.

개선

• Java String은 불변 클래스이므로 문자열 연산을 하게 될 때 해당 문자열 객체를 지웠다가 새로 만드는 굉장히 비효율적인 작업을 하게 된다. 따라서 StringBuilder를 사용하게 되는데 StringBuilder를 초기화하는 방법은 새로운 객체를 만들거나 delete연산을 사용하거나 StringBuilder의 객체 길이를 0으로 만드는 방법이 있다. 새로운 객체를 만들지 않고 delete 연산을 수행하지 않는, 길이를 0으로 만드는 방법이 가장 효율적인 초기화 방법이라고 한다.

코드

시간복잡도

• $O(N)$

C++

#include <iostream>
using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	string s;
	cin >> s;
	int sign = 1;
	string num = "";
	int ans = 0;
	for (auto c : s) {
		if (c == '-' || c == '+') {
			ans += sign * stoi(num);
			num.clear();
			if (c == '-')
				sign = -1;
			continue; 
		}
		num += c;
	}
	ans += sign * stoi(num);
	cout << ans;
}

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String line = sc.nextLine();
        int sign = 1;
        int ans = 0;
        StringBuilder sb = new StringBuilder();
        for (char c : line.toCharArray()) {
            if (c == '-' || c == '+') {
                ans += sign * Integer.parseInt(sb.toString());
                sb.setLength(0);
                if (c == '-')
                    sign = -1;
                continue;
            }
            sb.append(c);
        }
        ans += sign * Integer.parseInt(sb.toString());
        System.out.println(ans);
        sc.close();
    }
}