[BaekJoon/백준] 1541번 그리디 알고리즘

잃어버린 괄호문제.

 

나는 좀 어설프게 푼 것 같아서, 다른사람들의 풀이를 봤는데 문제에서 '같은 연산자가 연속으로 나올 수 없다'는 특징을 이용하신 것 같다.

 

일단 문제의 풀이 방향은

+ 먼저 계산 후 - 계산 이라고 보면 된다.

 

내 코드

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

class Main {
    public static void main(String args[]) throws Exception {

        // 50 - 40 + 30 - 20 - 10
        // 50, 40 + 30, 20, 10
        // - 로 토큰화한다음에, 각 토큰들을 +로 토큰화해서 계산.
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine(), "-");
        int key = 0;

        int c = stk.countTokens();
        for(int i = 0; i < c; i++) {
            StringTokenizer stk2 = new StringTokenizer(stk.nextToken(), "+");
            int temp = 0;
            int c2 = stk2.countTokens();
            for(int j = 0; j < c2; j++) {
                temp += Integer.parseInt(stk2.nextToken());
            }
            if(i == 0) // 맨 첫 경우는 초기값 세팅을 위한 작업.
                key = temp;
            else
                key -= temp;
        }
        System.out.println(key);
    }
}

 

 

다른분의 코드. 많은 분들이 이런식으로 풀었다. 동일한 부호가 연속해서 등장하지 않는다는 것?(10+20+30) 을 이용하신 것 같은데, 그런 특징이 없다면 내 코드와 달리 문제가 풀리지 않을수도...?! 아래 코드에서 신기한점은 C언어에서 문자열 형식으로 숫자를 받고, 그것을 숫자화시키기위해서 특정 연산을 사용한것이다.(atoi 같은 함수를 사용하면 바로 얻어낼 수도 있다 blockdmask.tistory.com/331)

#include <stdio.h>
int main()
{
    char arr[51];
    int s = 0, t = 0, i = 0, b = 1;
    scanf("%s", arr);
    while (arr[i] != '\0')
    {
        if (arr[i] == '-' || arr[i] == '+')
        {
            s += b * t;
            if (arr[i] == '-')
            {
                b = -1;
            }
            t = 0;
        }
        else // 321 이런 숫자일 경우, 3, 30+2, 320 + 1 이런식으로 만들어줌.
        {
            t = t * 10 + arr[i] - '0';
        }
        i++;
    }
    s += b * t;
    printf("%d\n", s);
    return 0;
}

else부분만 눈여겨보면 될 듯.. 나는 이 방법이랑 atoi 함수가 기억이 안나서 자바로 풀었다..