[백준] 1541번: 잃어버린 괄호 (JAVA)

이 문제 포스팅을 작성한 이유 키워드: Integer Parse / 약간의 동적 계획법

‼️이 문제의 정답 코드는 맨 마지막(Github Gist)에 있습니다. 중간중간의 코드들은 제 생각을 담은 일대기를 작성하였습니다.

첫번째 생각

맨 처음에 이 문제를 보고 든 생각은, 어떻게 빼는 수를 크게 할까? 였다.

괄호를 넣어서 '-' 부분을 극대화→식을 java 라이브러리로 계산하는 방법

을 생각하여 다음과 같이 코드를 작성하게 되었다.

import java.util.*;
import java.io.*;
import javax.script.ScriptEngineManager;
import javax.script.ScriptEngine;

public class Main {

   public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       String ss = br.readLine();
       StringBuilder s = new StringBuilder(ss);  //기존의 식
       StringBuilder s2 = new StringBuilder(ss); //괄호를 포함한 식
       int mode = 0;

       for(int i=0;i<s.length();i++) {
                //mode 1일 때: - 부분이 존재할 때
                //mode 0일 때: - 부분이 존재하지 않을 때
           if(s.charAt(i)=='-' & mode==0) { 
               mode =1;
               s2.insert(i+1, "(");
           }else if(s.charAt(i)=='-' & mode==1) {
               s2.insert(i+1, ")");
           }else if(mode == 1 & i==s.length()-1) {
               s2.append(")");
           }
       }
       System.out.println(s2.toString());
   }

}

하지만, java로 식을 계산하는 마땅한 라이브러리가 없었다. →그래서 포기

그래서 java 라이브러리 말고 직접 숫자를 읽어서 푸는 방법도 생각하였지만

1. 문제의 본질을 해친다는 생각
2. 1000자리 숫자는 어떻게 감당할 수 있을까..

하는 생각이 들어서 아예 다른 방법으로 접근하기로 생각했다.

두번째 생각

'-'를 기준으로 식을 분리한다는 문제의 본질에 맞추어 split을 통해 문장을 분리하고, 각각의 분리된 string에서 +를 따로 분리하여 작성하는 방법을 생각했다. 이를 바탕으로 코드를 작성하였다.

import java.util.*;
import java.io.*;

public class Main {

   public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       String[] s = br.readLine().split("\\-");
       **int res = Integer.parseInt(s[0]);**
       for(int i =1;i<s.length;i++) {
           int sum=0;
           String[] add = s[i].split("\\+");
           for(int l=0;l<add.length;l++) {
               sum += Integer.parseInt(add[l]);
           }
           res -= sum;
       }
       System.out.println(res);
   }

}

하지만, 계속해서 런타임 에러가 난다고 나왔고, 이에 split되어 계산되는 부분에 이상함을 느꼈다. 오류는 처음에 int res를 정의할 때 나타남을 감지하고 최종 코드를 작성하였다. 이와 더불어 클린 코드를 위해 함수를 따로 빼서 작성하였다.

이와 같이 작성되었을 때, 맞았다.

맞히고 나서 보니,

1. 기준으로 나뉘어 분리된 작은 문제들을 해결하는 면에서 동적 계획법을 생각해볼 수 있었고,
2. String → Integer Parse 부분에서의 대응법/처리 방법에 관해 한 층 더 깊게 생각해볼 수 있었다.