[알고리즘] 백준 1541 잃어버린 괄호 -그리디- 자바 코틀린

 

 

www.acmicpc.net/problem/1541

1541번: 잃어버린 괄호

 

백준 그리디 단계별풀기 마지막 문제인 잃어버린 괄호 문제입니다.

괄호를 추가해서 +,- 수식을 최솟값을 만들어야 합니다.

 

- 가 붙어 있다면 처음거는 더하고 그 뒤 부터는 쫙 뺴주면 됩니다. 

- 뒤에 -가 나올때까지 + 들을 괄호묶어서 최대값을 뺴줍니다.

 

예시를 남깁니다.

1 + 2 + 3 + 4 - 5 + 6 - 8 - 9 + 10 + 11

-> 1 + 2 + 3 + 4 - ( 5 + 6 ) - ( 8 ) - ( 9 + 10 ) + 11

 

1.  - 기준으로 분리한다.

2.  1에서 분리 한거를 + 기준으로 분리해준다.

3.  처음엔 - 가 안붙어 있으므로 더해주고 그 뒤 부터는 빼주면 됩니다.

 

 

다음은 풀이입니다.

[Java]

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        String[] minusArr = str.split("\\-");
        int result = 0;
        for (int i = 0; i < minusArr.length; i++) {
            String[] plusArr = minusArr[i].split("\\+");
            for (int j = 0; j < plusArr.length; j++) {
                if (i == 0) {
                    result += Integer.parseInt(plusArr[j]);
                } else {
                    result -= Integer.parseInt(plusArr[j]);
                }
            }
        }
        System.out.println(result);
    }
}

 

 

[Kotlin]

import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val str = sc.nextLine()
    val minusArr = str.split("\\-".toRegex()).toTypedArray()
    var result = 0
    for (i in minusArr.indices) {
        val plusArr = minusArr[i].split("\\+".toRegex()).toTypedArray()
        for (j in plusArr.indices) {
            if (i == 0) {
                result += plusArr[j].toInt()
            } else {
                result -= plusArr[j].toInt()
            }
        }
    }
    println(result)
}

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!