[백준] S2 1541번 잃어버린 괄호 (Java)

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

해당 문제는 'Do it! 알고리즘 코딩테스트 자바 편'을 보면서 공부한 내용입니다.

👉 문제

문제 분석에 앞서 그리디 알고리즘은 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘입니다.

그리디는 다음의 3단계를 반복하면서 문제를 해결합니다.

그리디 알고리즘 수행 과정
1. 해 선택: 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다.
2. 적절성 검사: 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사한다.
3. 해 검사: 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다. 전체 문제를 해결하지 못한다면 1로 돌아가 같은 과정을 반복한다.

하여 이 문제는 그리디의 관점에서 생각하면 쉽게 풀 수 있는 문제라고 합니다.

가장 작은 최솟값을 만들기 위해서는 가능한 큰 수를 빼야 합니다. 그렇다면 빼기와 더하기 사이에서 빼기 뒤에 있는 더하기로 이루어진 수들을 전부 괄호를 쳐서 먼저 계산한 후 빼기를 하면 될 것입니다.

대략적인 알고리즘은 다음과 같습니다.

1. 들어온 데이터를 "-" 기호를 기준으로 split() 수행하기

2. 나눠진 String값을 "+" 기호 기준으로 split() 수행하기

👉 풀이

import java.util.Scanner;

public class P1541_잃어버린괄호_1 {
    static int answer = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String input = sc.nextLine();
        String[] str = input.split("-");

        for (int i = 0; i < str.length; i++) {
            int temp = mySum(str[i]);
            if (i == 0)
                answer += temp; // 가장 앞에 있는 값만 더함
            else
                answer -= temp; // 뒷부분은 더했던 값들을 모두 뺌
        }
        System.out.println(answer);
    }

    static int mySum(String s) {
        int sum = 0;
        String[] temp = s.split("\\+");

        for (int i = 0; i < temp.length; i++) {
            sum += Integer.parseInt(temp[i]);
        }

        return sum;
    }
}

👉 성능