출처
백준 - 잃어버린 괄호
🔎 문제
세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.
그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.
괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.
🚫 입력 및 출력
<입력>
첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.
<출력>
첫째 줄에 정답을 출력한다.
💻 입출력 예
📄🤔 코드 및 풀이과정
🔹 1번
import java.util.Scanner;
public class BaekJoon1541 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String input = scanner.nextLine();
int sum = 0;
int tempSum = 0;
String[] arr = input.split("\\-");
String[] temp = arr[0].split("\\+");
if(temp.length != 1) { //첫 기호가 +일때
for (int i = 0; i < temp.length; i++) {
sum+=Integer.parseInt(temp[i]);
}
}else { //첫 기호가 -일때
sum = Integer.parseInt(temp[0]);
}
for (int i = 1; i < arr.length; i++) {
temp = arr[i].split("\\+");
if(temp.length != 1) { //+기호가 있을 때
for (int k = 0; k < temp.length; k++) {
tempSum += Integer.parseInt(temp[k]);
}
sum -= tempSum;
tempSum=0;
}else { //+기호가 없을 때
sum -= Integer.parseInt(temp[0]);
}
}
System.out.println(sum);
}
}🔸 1번 풀이
처음 코드는
먼저 '-' 연산자를 구분자로 split을 하고,
split하여 나온 첫번째 요소의 계산식을 계산한 값을
sum에 저장하도록 했다.
처음에 연속적으로 나오는 '+' 연산자들은 결과값을 적게 만드는데 쓰일 수 없기에
첫 '-' 연산자가 나오기 전까지는 앞의 수들을 모두 더한다.
첫 '-' 연산자가 나온 이후에는
'+' 연산자로 인해 결과값이 커지는 일이 없도록
'+' 연산자로 이어지는 수들끼리 괄호로 묶어 더해주고,
'-' 연산자가 이를 결과값에서 빼도록 구현했다.
예를 들어
11+50-20+30+40-10+20-10
이 입력값으로 들어올 경우
11+50-(20+30+40)-(10+20)-10
처럼 '+' 연산자로 이어지는 수들을 괄호로 묶게 되면
첫 '-' 연산자 이후로는 무조건 결과값이 감소가 되는 방식이다.
이러한 로직을 구현하여 통과했으며
메모리 12840KB / 처리시간 108ms 가 나왔다.
🔹 2번
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class BaekJoon1541 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String input = br.readLine();
int sum = 0;
String[] arr = input.split("\\-");
String[] temp = arr[0].split("\\+");
if(temp.length != 1) {
for (int i = 0; i < temp.length; i++) {
sum+=Integer.parseInt(temp[i]);
}
}else {
sum = Integer.parseInt(temp[0]);
}
for (int i = 1; i < arr.length; i++) {
temp = arr[i].split("\\+");
if(temp.length != 1) {
for (int k = 0; k < temp.length; k++) {
sum -= Integer.parseInt(temp[k]);
}
}else {
sum -= Integer.parseInt(temp[0]);
}
}
System.out.println(sum);
}
}🔸 2번 풀이
알고리즘 문제를 최대한 다양한 방식으로 풀어보고 난 뒤
추가적인 공부를 위해 다른 사람들의 코드를 보면
많은 사람들이 Scanner가 아닌 BufferedReader로 입력을 받고 있었다.
나는 지금까지 Scanner가 메서드로 인한 편의성이 좋고 속도면에서 BufferedReader보다 Scanner이 좀 더 빠르다고 알고 있어 항상 Scanner를 사용했었다.
하지만 다들 BufferedReader를 사용하는 것을 보고 이상함을 느껴 여기저기 찾아본 결과 잘못된 지식을 가지고 있었다는걸 알게 되었다.
Scanner의 경우 1024chars의 버퍼
BufferedReader의 경우 8192chars의 버퍼를 가지고 있어
많은 양의 데이터를 입력받을 경우 큰 버퍼를 가진 BufferedReader가 유리하며
Scanner는 여러 메서드를 지원하며 구분자로 파싱이 가능해 편리한 대신,
입력값을 정규표현식으로 체크를 하기 때문에 불필요하게 처리시간이 늘어난다.
BufferedReader는 입력값 체크 없이 바로 String형태로 받아들이기 때문에 Scanner보다 빠르게 처리가 가능하다.
각자의 장단점이 있기 때문에 무조건 BufferedReader를 써야지! 는 아니기에
상황에 따라 어느 쪽이 나은지 고려해보며 사용해야겠다.
메모리 11508KB / 처리시간 76ms 으로 통과했으며
1번처럼 Scanner를 사용했을 때보다 처리시간이 32ms나 줄어들었다.
🔹 3번
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class BaekJoon1541 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String input = br.readLine();
int result = 0;
String[] arr = input.split("\\-");
String[] temp = arr[0].split("\\+");
for (int i = 0; i < temp.length; i++) {
result+=Integer.parseInt(temp[i]);
}
for (int i = 1; i < arr.length; i++) {
temp = arr[i].split("\\+");
for (int k = 0; k < temp.length; k++) {
result -= Integer.parseInt(temp[k]);
}
}
System.out.println(result);
}
}🔸 3번 풀이
2번 방법까지 해보고, 처리시간 줄였다! 내일 아침부터 바쁘니 이만 자야지~
하고 침대에 누운 순간 머리를 스쳐지나가는 생각이 있었다.
"생각해보니 구지여 연산자에 따라 조건별로 처리할 필요가 있나?"
"조건문 지우고 연산자가 '+' 든 '-' 든 같은 for문으로 처리하면 되는거 아냐...?"
당장 이불을 박차고 나와 연산자별로 조건을 나누는 if-else문을 모조리 지워버리고 로직을 다시 체크해봤다. 전혀 문제가 없었다. 결과도 당연하다는 듯이 통과해버렸다.
1번 문제를 풀 때 까지만 해도 연산자에 따라서 조건을 나눠서 풀어야겠다
라는 생각을 하고 풀었던게 또 머리를 굳어지게 한 것 같다.
조건문을 만나는 횟수가 그렇게 많지는 않은 문제라
메모리 11560KB / 처리시간 80ms 로 2번과 크게 다르지 않은 속도지만
불필요한 조건문들이 싹 사라져 코드가 훨씬 간결해지며 가독성이 좋아졌다.
😳❕ 소감 & 느낀점
이번 알고리즘을 풀면서 얻은 가장 큰 수확은 Scanner와 BufferedReader의 차이를 정확하게 알게 된 것이 아닐까 한다.
처음 자바를 배울 땐 Scanner가 훨씬 편하기도 하고 어디선가 잘못된 지식으로 Scanner가 더 빠르다고 생각해 Scanner만 사용해왔었다.
하지만 이번 알고리즘을 풀면서 잘못된 지식이라는 것을 알 수 있었고
앞으로 좀 더 BufferedReader를 많이 활용해봐야겠다고 느꼈다.
또한 3번의 경험으로 불필요한 로직이 자연스럽게 껴있지 않은가에 대한 의심을 항상 가지자고 생각했다.
나는 당연히 필요하다고 생각했던 부분인데
곰곰히 생각해보니 전혀 필요가 없는 부분이였다
라는게 앞으로 한 두번 있을 일이 아닐 것이다.
아직 새내기 개발자이기 때문에
첫 코드부터 바로 효율성이 좋은 코드는 작성하지 못하지만,
개선하기 위한 노력을 아끼지 않으며 조금이라도 더 효율성 높은 코드를 작성하려 하는 개발자가 되고 싶다.
