[백준] 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를 정의할 때 나타남을 감지하고 최종 코드를 작성하였다. 이와 더불어 클린 코드를 위해 함수를 따로 빼서 작성하였다.

	//최종 코드
	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[] s = br.readLine().split("\-");
	int ress=summ(s[0]);
	for(int i =1;i<s.length;i++) {
	//summ에서 최대 숫자를 최종 결과인 ress에서 빼게 된다.
	ress -= summ(s[i]);
	}
	System.out.println(ress);
	}
	//+만이 존재하는 부분을 처리하는 summ 함수
	public static int summ(String s) {
	int res=0;
	String[] add = s.split("\+");
	for(int l=0;l<add.length;l++) {
	res += Integer.parseInt(add[l]);
	}
	return res;
	}
	}

view raw BOJ_1541 hosted with ❤ by GitHub

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

맞히고 나서 보니,

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