[백준 1541번] 잃어버린 괄호

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

1541번: 잃어버린 괄호

문제

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.

그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.

괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

입력

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.

출력

첫째 줄에 정답을 출력한다.

예제 입력 1 

55-50+40

예제 출력 1 

-35

예제 입력 2 

10+20+30+40

예제 출력 2 

100

예제 입력 3 

00009-00009

예제 출력 3 

0

 

 

문제 분석

연산을 할 때 최솟값을 만들기 위해서는 가장 큰 수를 빼는 것입니다.

덧셈(+)으로 이루어진 부분을 먼저 계산한 뒤 빼주는 것입니다.

1. 뺄셈(-)을 기준으로 문자열을 분리해줍니다.
2. 분리된 문자열들 각각에 포함된 정수 값들을 모두 더 해줍니다.
3. 2번 값들을 뺄셈 해줍니다. (맨 앞 정수는 양수입니다.)

 

String클래스의 split메서드를 이용해서 문자열을 파싱 해보겠습니다.

    * 파싱이란? 가공되지 않은 데이터에서 원하는 특정한 문자열을 빼내는 작업을 말합니다. 

 

✔ 문자열 파싱법
1. 몇 번째 ~ 몇 번째까지 index에 해당하는 부분을 문자열로 뽑아내고 싶다면
   -> String클래스의 substring
2. 구분자가 중간중간에 위치해있어, 특정 구분자를 기준으로 문자열을 자르고 싶다면
   -> String클래스의 split메서드 또는 StringTokenizer클래스를 사용하면 됩니다.

 

 

문자열 파싱법을 토대로 코드 구현을 해보았을 때, 출력이 안 나오는 것을 확인할 수 있습니다.

split은 정규표현식으로 문자를 분리하는데 정규표현식에서 점(.)은 일종의 메타문자이기 때문입니다.

 

메타문자가 아닌 문자 그대로 구분자로 사용하고 싶다면 이스케이프 문자인 ＼＼을 앞에 붙여주어야 합니다.

그러면 결과가 제대로 파싱 되는 것을 확인할 수 있습니다.

String str = "lealea.tistory.com";
String[] strArr = str.split(".");
	for(String s : strArr) {
		System.out.println(s);
	}
    
// 출력

 

수정 후

String str = "lealea.tistory.com";
String[] strArr = str.split("\\.");
	for(String s : strArr) {
		System.out.println(s);
	}
        
// 출력 
lealea
tistory
com

 

 

위에서 'split은 정규표현식으로 문자를 분리하는데 정규표현식에서 점(.)은 일종의 메타문자이기 때문입니다.'

라고 적었습니다. 이어서 메타문자란 무엇인지 알아보도록 하겠습니다.

💡 메타문자란? 메타 문자 split 하는 방법
메타 문자란 정규 표현식에서 사용하는 문자입니다.

여기서 생소한 개념은 '메타 문자', '정규표현식'인데요.

우선 정규표현식은 복잡한 문자열을 처리할 때 사용하는 기법입니다.
우리가 원하는 특정한 패턴을 찾을 때, 패턴을 다른 문자열로 바꿀 때뿐만 아니라
이메일, 패스워드를 입력할 때 특정 패턴 유효성 검사로도 사용합니다.

예를 들어 ' 핸드폰 번호를 포함하고 있는 텍스트가 있습니다. 이 텍스트에 포함된 모든 핸드폰 번호 뒷자리를 *문자로 변경해주세요.'를  정규표현식을 이용하면 가독성 높게 코드 구현을 할 수 있습니다. 

두 번째로 알아볼 개념은 메타 문자입니다.
원래 그 문자가 가진 뜻이 아니라 특별한 용도로 사용되는 것을 말합니다.

Chracter	뜻
|	또는
( )	그룹
[ ]	문자셋, 괄호 안의 어떤 문자든
[^]	부정 문자셋, 괄호 안의 어떤 문자가 아닐 때
(?:)	찾지만 기억하지는 않음
?	없거나 있거나 (zero or one)
*	없거나 있거나 많거나 (zero or more)
{n}	n번 반복
{min,}	최소
{min, max}	최소, 그리고 최대
／b	단어 경계
／B	단어 경계가 아님
^	문장의 시작
$	문장의 끝
／	특수 문자가 아닌 문자
.	어떤 글자 (줄 바꿈 문자 제외)
／d	digit 숫자
／D	digit 숫자 아님
／w	word 문자
／W	word 문자 아님
／s	space 공백
／S	space 공백 아님

[메타 문자에 split 처리하는 방법]
메타 문자 중 ?, *, +, ( ), [ ], { }는 split이 불가능합니다.
split을 하기 위해서는 메타 문자 앞에 역 슬래쉬 2개 ＼＼를 붙이는 이스케이프 처리가 필요합니다.

 

오늘은 알아볼 개념들이 많았습니다. 처음에는 머릿속에 넣어야 할 개념이 많지만

이렇게 몇 번 하다 보면 어느새 성장해있길 바랍니다.

 

성공 코드

중간중간 출력을 찍어보면서 따라가 보겠습니다. 

import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner kb = new Scanner(System.in);
		String str = kb.next(); // 55-50+40
		String[] strArr = str.split("-"); 
		System.out.println("strArr : " + Arrays.toString(strArr)); // [55, 50+40]
		int sum = Integer.MAX_VALUE;
		for(int i =0; i<strArr.length; i++) {
			String[] substraction = strArr[i].split("\\+"); 
			System.out.println("substraction: " + Arrays.toString(substraction)); // [55] / [50, 40]
			
			// -연산 모아둘 임시 변수
			int tmp =0 ;
			
			for(int j=0; j<substraction.length; j++) {
				tmp += Integer.parseInt(substraction[j]);
				System.out.println("tmp :" +tmp); // 55 / 50 90
			}
			
			if(sum == Integer.MAX_VALUE) {
				sum = tmp; // 첫 번째 토큰이 sum으로 들어감
				System.out.println("첫 번째 토큰:" + sum); // 55
			}else {
				sum -= tmp;
			}	
		}
		
		System.out.println(sum); // -35
		
	}

}

 

출력

입력)
55-50+40

출력)
strArr : [55, 50+40]
substraction: [55]
tmp :55
첫 번째 토큰:55
substraction: [50, 40]
tmp :50
tmp :90
-35

 

 

출력을 전부 지운 성공 코드입니다.

import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner kb = new Scanner(System.in);
		String str = kb.next();
		String[] strArr = str.split("-"); 
		int sum = Integer.MAX_VALUE;
        
		for(int i=0; i<strArr.length; i++) {
			String[] substraction = strArr[i].split("\\+"); 
			
			int tmp =0 ;
			
			for(int j=0; j<substraction.length; j++) {
				tmp += Integer.parseInt(substraction[j]);
			}
			
			if(sum == Integer.MAX_VALUE) {
				sum = tmp; 
			}else {
				sum -= tmp;
			}
		}
		
		System.out.println(sum);

	}

}

 

참고:

https://st-lab.tistory.com/148

---

 

 

[[ 문제를 분석하면서 헷갈리거나 생소한 기본 개념들을 각각 포스팅하였습니다. 도움이 되셨으면 합니다^^ ]]

 

1. String클래스 메서드

String 클래스 메서드

String 클래스 메서드

 

2. StringTokenizer클래스

Scanner보다 빠른 입력 BufferedReader, StringTokenizer

Scanner보다 빠른 입력 BufferedReader, StringTokenizer

 

3. Arrays클래스 메서드

Arrays 클래스

Arrays 클래스

 

4. 형변환 (문자형 ↔ 정수형  ↔ 실수형)

형변환 (문자형↔정수형↔실수형)

형변환 (문자형↔정수형↔실수형)

 

5.  Scanner 클래스에서 next(), nextLine() 메서드는 String 타입으로 리턴해줍니다.

public class Example {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
        
		System.out.println("nextLine: ");
		String str1 = scanner.nextLine();
		System.out.println(str1);
        
		System.out.println("next: ");
		String str2 = scanner.next();
		System.out.println(str2);
	}
}

// 결과
nextLine :
안녕하세요 반갑습니다 <- 입력값
안녕하세요 반갑습니다 <- 출력된 형태
next : 
안녕하세요 반갑습니다 <- 입력값
안녕하세요 <- 출력된 형태

nextLine()메서드는 Enter를 치기 전까지 쓴 문자열을 모두 리턴,

next() 메소드는 Space 즉 공백 전까지 입력받은 문자열을 리턴합니다.

공백이 있는 한 줄을 리턴 받고 싶으면 nextLine() 메서드를 사용하고, 한 단어만 리턴받고 싶으면 next() 메소드를 사용하면 됩니다.