Baekjoon #1541 잃어버린 괄호

잃어버린 괄호

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

1541번: 잃어버린 괄호

 

문제

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다. 그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다. 괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

입력

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.

 

출력

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

---

그리디 알고리즘을 이용하는 문제이다.

매 계산마다 답에 가까워지는 최적의 중간값으로만 가도록 하여 해결할 수 있다.

 

그리디 알고리즘은 어떻게 보면 빠르게 수행되어 답을 찾을 수 있지만

항상 그 방법이 최적해라는 것을 보장하지는 않는다.

 

나는 아직 수학적으로 생각하는 것에 익숙치가 않은 것 같다. 직관적으로 생각해서 풀었다...

 

+ 짜잘한 메모

언덕 오르기 기법 (hill climbing method)

인공지능에서 쓰이는 기법이기는 하지만, 이것 역시 그리디 알고리즘이 기초이다. (그러나 언덕을 잘 못타게 되면, local optimal solution에 빠질 수 있다.)

 

다시 말하지만 위 문제와는 관계없는 이야기다!!!!!

---

풀이

뺄셈의 결과값이 작으려면 빼짐을 당하는 수는 작아야 되고, 빼는 수는 커야한다.

 

분할 정복처럼 '-'로 분리해주면 문제는 A 1개, B 여러개를 구하는 것으로 축약될 수 있다.

answer // 최종 출력할 값 minusTokens // 문자열을 '-'로 나눈 토큰들 while (hasMoreMinusTokens) {     plusTokens = minusToken을 '+'로 나눈 결과 토큰들     while (hasMorePlusTokens) {         number = plusToken     }     // 처음 수 (A 인지 확인)이면 + 계산     if 처음 수 : answer += number     // 2번째 부터는 B 이므로 '-' 계산     else : answer -= number }

직관적으로 생각해서 코드를 짜면 이렇다.

단지 이중 반복문이고 문자열 분리를 자주하기 때문에 시간이 다소 걸릴 수 있는 risk가 있다.

---

전체 코드

/*
* 잃어버린 괄호
* https://www.acmicpc.net/problem/1541
* */

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

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

        int answer = 0;
        int t = 0;
        boolean firstNumberFlag = false;
        StringTokenizer st = new StringTokenizer(br.readLine(), "-");
        while(st.hasMoreTokens()) {
            StringTokenizer st2 = new StringTokenizer(st.nextToken(), "+");
            while (st2.hasMoreTokens()) {
                t += Integer.parseInt(st2.nextToken());
            }
            if (!firstNumberFlag) {
                firstNumberFlag = true;
                answer += t;
            }
            else {
                answer -= t;
            }
            t = 0;
        }

        System.out.println(answer);

        br.close();
    }
}