[*1541*] 잃어버린 괄호 in Java

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

1541번: 잃어버린 괄호

괄호 관련 문제

https://eboong.tistory.com/600

[16637] 괄호 추가하기 in Java

https://eboong.tistory.com/405

[n11899] 괄호 끼워넣기 in python

---

문제 : 괄호를 적절히 쳐서 이 식의 값을 최소로 만들기

---

문제 접근 방식

 

괄호를 쳐서 식의 값을 최소로 만드는 것이 이 문제의 핵심이다.

 

처음에는 괄호 추가하기 문제처럼풀었는데 실패했다...

 

그래서 구글링을 해보니..아주 간단한 문제였다 +_+

 

가능한 모든 숫자들을 빼주는 것이우리가 원하는 값을 얻을 수 있는 방법이다.

 

 

10-20+30-40 따라서 -를 기준으로 문자열을 쪼개준다

[10, 20+30, 40]

 

그리고 이번에는 위 배열의 원소들 중에 +가 있는 경우는

+를 기준으로 문자열을 쪼개준다

 

answer = 0

i==0일때, 10

맨 앞에 있는 숫자는 무조건 + 이기 때문에 answer+=10

 

i==1일때 20+30

[20,30]

각 원소를 20+30=50와 같이 모두 더해준다.

answer에는 50을 거꾸로 빼주면 된다.

 

i==2일때, 40

answer에는 40을 거꾸로 빼준다.

 

그럼 최종값은 -80이 된다.

 

 

 

참고로 split("\\+");에 \\를 넣어주는 이유는

컴파일 에러를 방지하기 위함

 

https://jainn.tistory.com/346

[백준] 1541번:잃어버린 괄호(Java 자바)

 

---

시행 착오

https://eboong.tistory.com/600

[*16637*] 괄호 추가하기 in Java

 

위 문제에서 푼 방식대로

dfs 방식으로 괄호를 추가해보려고 했는데

잘 안됐다...

 

시간 내서 다시 도전해볼 것.

 

 

---

 

16637번 문제에서 쓴 알고리즘을 활용해보려고 했는데

0-100+50-100+50-100 케이스에서

오류 나옴 

(출력 : -200, 정답 : -400)

 

틀린 코드 . . 왜 틀렸지 ㅎ..

static int answer;
    static List<Integer> numList;
    static List<Character> operList;
    
    public static int calculate(int a, int b, char op) { // 계산하기
        if(op=='+') return a+b;
        else return a-b;
        
    }
    
    public static void dfs(int opidx, int sum) { // 현재 연산자 인덱스, 직전 재귀 함수에서 계산한 값
        if(opidx==operList.size()) { // 연산자를 모두 사용한 경우
            answer=Math.min(answer, sum); // 최댓값을 구하기 위해 max 함수 사용
            return;
        }
        // 괄호가 없는 경우
        // 정상적으로 앞에서부터 차례대로 계산하는 과정
        int result1=calculate(sum, numList.get(opidx+1), operList.get(opidx));
        dfs(opidx+1, result1); // 연산자 1개 사용했으니 인덱스 +1 증가, 위에서 계산한 값 넘겨주기
        
        // 괄호가 있는 경우
        // 맨 뒤부터 괄호를 묶어준다.
        // opidx가 맨 끝이 아닐 경우에만 괄호를 넣어준다.
        if (opidx+1<operList.size()) {
            int result2=calculate(numList.get(opidx+1),numList.get(opidx+2) , operList.get(opidx+1));
            dfs(opidx+2,calculate(sum, result2, operList.get(opidx)));
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String inputS=br.readLine();
        String temp="";
        numList=new ArrayList<>(); // 숫자 리스트
        operList=new ArrayList<>(); // 연산자 리스트
        for (int i = 0; i < inputS.length(); i++) {
            // 연산자일 경우
            if(inputS.charAt(i)=='+' || inputS.charAt(i)=='-') {
                if (temp!="") {
                    numList.add(Integer.parseInt(temp));
                    temp="";
                }
                operList.add(inputS.charAt(i));
            }
            // 숫자일 경우
            else {
                temp+=inputS.charAt(i);
            }
        }
        answer=Integer.MAX_VALUE;
        if(temp!="") numList.add(Integer.parseInt(temp));
        dfs(0,numList.get(0));
        System.out.println(answer);
    }

 

 

 

---

소스 코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
 
public class Main {
    static int answer;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputArr=br.readLine().split("-");
        
        int answer=0;
        for (int i = 0; i < inputArr.length; i++) {
            String[] plusArr=inputArr[i].split("\\+");
            int temp=0;
            for (int j = 0; j < plusArr.length; j++) {
                temp+=Integer.parseInt(plusArr[j]);
            }
            if (i==0) answer+=temp;
            else answer-=temp;
        }
        System.out.println(answer);
    }
}