[백준] 1541번 : 잃어버린 괄호 - JAVA [자바]

www.acmicpc.net/problem/1541

1541번: 잃어버린 괄호

 

---

• 문제

 

 

 

 

 

이 번 문제 또한 그리 어렵지 않게 풀 수 있는 문제다. 문제만 잘 이해한다면 금방 이해할 수 있을 것이다.

 

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

 

 

위 문제에서 주어지는 예제는 다음과 같다.

55-50+40

 

그럼 여러분들은 아주 쉽게 괄호를 쳐서 '최솟값'을 다음과 같이 만들 수 있다.

55-(50+40)

 

그럼 정답은 -35가 된다.

 

다른 예시들을 보자.

30-70-20+40-10+100+30-35 가 있다고 생각해보자. 그럼 최솟값은 어떻게 되어야 할까?

당연히 최솟값을 만들기 위해서는 최대한 '큰 수'를 빼주어야 한다. 즉, 덧셈(+)으로 이루어진 부분을 먼저 계산한 뒤 빼주는 것이다. 이를 적용하여 괄호를 치면 다음과 같을 것이다.

 

30-70-(20+40)-(10+100+30)-35

그럼 정답은 -275가 될 것이다. 한마디로 포인트는 '덧셈 부분을 먼저 계산 하는 것'이다.

 

알고리즘은 문자열을 분리해주는 split()함수나 StringTokenizer클래스를 사용하여 쉽게 풀 수 있으니 그리 어렵지 않게 만들 수 있다. 크게 다음과 같은 세 가지 과정을 거친다.

 

1. 뺄셈(-)을 기준으로 1차적으로 문자열을 분리해준다.

2. 분리된 문자열들 각각에 포함 된 정수 값들을 모두 더 해준다.

3. 각각 더해진 값들을 뺄셈해준다.

 

쉽게 그림으로 보자면 다음과 같다.

 

 

뺄셈기호(-)를 중심으로 먼저 문자열을 분리해준 뒤, 각 분리된 문자열안에 있는 정수끼리 더해준다. 그 다음 분리된 문자열들을 뺄셈을 해주면 되는 것이다.

 

이 때 주의해야 할 점은 '첫 번째 수는 양수'라는 점이다. 만약 모조리 빼버리면 첫 번째 수도 음수가 되어 결과값이 -335가 되어버리는 잘못된 답이 나온다. 이를 유의하여 코딩해야 한다.

 

 

 

자바 코드로는 앞서 split함수와 StringTokenizer 이렇게 두 가지 방식이 있다고 했다. 즉, 다음과 같이 두 가지 알고리즘을 짤 수 있다.

 

[split() 메소드]

int sum = Integer.MAX_VALUE;	// 초기 상태 여부 확인을 위한 값으로 설정 
String[] subtraction = br.readLine().split("-");
		

for(int i = 0; i < subtraction.length; i++) {
	int temp = 0;

	// 뺄셈으로 나뉜 토큰을 덧셈으로 분리하여 해당 토큰들을 더한다.
	String[] addition = subtraction[i].split("\\+");
			
	// 덧셈으로 나뉜 토큰들을 모두 더한다. 
	for(int j = 0; j < addition.length; j++) {
		temp += Integer.parseInt(addition[j]);
	}
			
	// 첫 번째토큰인 경우 temp값이 첫 번째 수가 됨
	if (sum == Integer.MAX_VALUE) {
		sum = temp;
	} else {
		sum -= temp;
	}
}

 

여기서 주의해야 할 점은 split의 경우 정규식(regex)을 받기 때문에 "+"을 하면 regex.PatternSyntaxException을 뱉는다.

+ 문자가 메타문자(meta character)라 그렇다.(=특별한 의미를 담고 있다는 뜻) 

그렇기 때문에 온전하게 문자 그 자체로 이용하기 위해서는 이스케이프 처리를 해야한다. 하지만 \(백슬래시)도 단독으로 출력할 수 없기 때문에 백슬래시 자체도 이스케이프 해야한다. 즉 \\+ 를 해야 우리가 분리하고자 하는 "+" 문자 그대로 분리할 수 있다.

 

 

 

[StringTokenizer]

int sum = Integer.MAX_VALUE;	// 초기 상태 여부 확인을 위한 값으로 설정 
StringTokenizer subtraction = new StringTokenizer(br.readLine(), "-");

while (subtraction.hasMoreTokens()) {
	int temp = 0;

	// 뺄셈으로 나뉜 토큰을 덧셈으로 분리하여 해당 토큰들을 더한다.
	StringTokenizer addition = new StringTokenizer(subtraction.nextToken(), "+");
			
	// 덧셈으로 나뉜 토큰들을 모두 더한다. 
	while (addition.hasMoreTokens()) {
		temp += Integer.parseInt(addition.nextToken());
	}
			
	// 첫 번째토큰인 경우 temp값이 첫 번째 수가 됨
	if (sum == Integer.MAX_VALUE) {
		sum = temp;
	} else {
		sum -= temp;
	}
}

 

 

이렇게 두 가지 버전 중 여러분들이 편한 것을 사용하면 된다.

 

 

 

 

 

 

 

 

 

 

---

• 4가지 방법을 사용하여 풀이한다.

 

 

Scanner 와 BufferedReader 각각의 입력방법을 통해 위에서 설명한 두 알고리즘을 적용하여 풀어보도록 하겠다.

 

 

1 . Scanner + split

2. Scanner + StringTokenizer

3. BufferedReader + split

4. BufferedReader + StringTokenizer

 

 

 

 

---

• 풀이

- 방법 1 : [Scanner + split]

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);

		int sum = Integer.MAX_VALUE;	// 초기 상태 여부 확인을 위한 값으로 설정 
		String[] subtraction = in.nextLine().split("-");
		

		for(int i = 0; i < subtraction.length; i++) {
			int temp = 0;

			// 뺄셈으로 나뉜 토큰을 덧셈으로 분리하여 해당 토큰들을 더한다.
			String[] addition = subtraction[i].split("\\+");
			
			// 덧셈으로 나뉜 토큰들을 모두 더한다. 
			for(int j = 0; j < addition.length; j++) {
				temp += Integer.parseInt(addition[j]);
			}
			
			// 첫 번째토큰인 경우 temp값이 첫 번째 수가 됨
			if (sum == Integer.MAX_VALUE) {
				sum = temp;
			} else {
				sum -= temp;
			}
		}
		System.out.println(sum);
	}

}

 

 

가장 기본적인 방법이라 할 수 있겠다.

 

 

 

 

---

- 방법 2 : [Scanner + StringTokenizer]

 

 

 

입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다. 단, BufferedReader 는 문자열을 한 줄로 읽기 때문에 N과 M을 구분하기 위해 공백을 기준으로 문자열을 분리해주어야하니 StringTokenizer 을 사용하여 풀도록 하겠다.

 

 

import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);

		int sum = Integer.MAX_VALUE;	// 초기 상태 여부 확인을 위한 값으로 설정 
		StringTokenizer subtraction = new StringTokenizer(in.nextLine(), "-");

		while (subtraction.hasMoreTokens()) {
			int temp = 0;

			// 뺄셈으로 나뉜 토큰을 덧셈으로 분리하여 해당 토큰들을 더한다.
			StringTokenizer addition = new StringTokenizer(subtraction.nextToken(), "+");
			
			// 덧셈으로 나뉜 토큰들을 모두 더한다. 
			while (addition.hasMoreTokens()) {
				temp += Integer.parseInt(addition.nextToken());
			}
			
			// 첫 번째토큰인 경우 temp값이 첫 번째 수가 됨
			if (sum == Integer.MAX_VALUE) {
				sum = temp;
			} else {
				sum -= temp;
			}
		}
		System.out.println(sum);
	}

}

 

 

 

위에서 설명한 알고리즘 그대로 갖고온 것이므로 부가적으로 설명할 것은 없을 것이다.

크게 어려울 것은 없을 것이다. 이번 문제는 중복을 고려하지 않아도 되니 오히려 쉬웠을 수도 있다.

 

 

 

---

- 방법 3 : [BufferedReader + split]

 

 

 

입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다. 

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int sum = Integer.MAX_VALUE;	// 초기 상태 여부 확인을 위한 값으로 설정 
		String[] subtraction = br.readLine().split("-");
		

		for(int i = 0; i < subtraction.length; i++) {
			int temp = 0;

			// 뺄셈으로 나뉜 토큰을 덧셈으로 분리하여 해당 토큰들을 더한다.
			String[] addition = subtraction[i].split("\\+");
			
			// 덧셈으로 나뉜 토큰들을 모두 더한다. 
			for(int j = 0; j < addition.length; j++) {
				temp += Integer.parseInt(addition[j]);
			}
			
			// 첫 번째토큰인 경우 temp값이 첫 번째 수가 됨
			if (sum == Integer.MAX_VALUE) {
				sum = temp;
			} else {
				sum -= temp;
			}
		}
		System.out.println(sum);
	}

}

 

 

 

 

---

- 방법 4 : [BufferedReader + StringTokenizer]

 

 

 

 

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int sum = Integer.MAX_VALUE;	// 초기 상태 여부 확인을 위한 값으로 설정 
		StringTokenizer subtraction = new StringTokenizer(br.readLine(), "-");

		while (subtraction.hasMoreTokens()) {
			int temp = 0;

			// 뺄셈으로 나뉜 토큰을 덧셈으로 분리하여 해당 토큰들을 더한다.
			StringTokenizer addition = new StringTokenizer(subtraction.nextToken(), "+");
			
			// 덧셈으로 나뉜 토큰들을 모두 더한다. 
			while (addition.hasMoreTokens()) {
				temp += Integer.parseInt(addition.nextToken());
			}
			
			// 첫 번째토큰인 경우 temp값이 첫 번째 수가 됨
			if (sum == Integer.MAX_VALUE) {
				sum = temp;
			} else {
				sum -= temp;
			}
		}
		System.out.println(sum);
	}

}

 

 

 

크게 어려울 것은 없을 것이다. 이번 문제는 중복을 고려하지 않아도 되니 오히려 쉬웠을 수도 있다.

 

 

 

 

 

---

• 성능

 

채점 번호 : 23110402  -  방법 4 : BufferedReader + StringTokenizer

채점 번호 : 23110396  -  방법 3 : BufferedReader + split

채점 번호 : 23110392  -  방법 2 : Scanner + StringTokenizer

채점 번호 : 23110388  -  방법 1 : Scanner + split

 

 

입력의 경우는 확실히 Scanner 보다는 BufferedReader 가 빠른 걸 볼 수 있다.

또한 StringTokenizer가 split보다 빠른데, 이는 spilt의 구조상 정규식을 인자로 받기 때문에 오버헤드가 커서 그렇다. (하지만 현장(?)에서는 정규식을 쓰는 것이 더욱 안전하고, 권장하는 방법이니 두 방법 모두 알고 있길 바란다.)

---

• 정리

 

이 번 문제는 워낙 쉬워서.. 그렇다할 설명할 것이 별로 없었다. 그나마 유의할 점이라면 split함수를 쓰기 위해서 조심해야 할 점들이 있다는 것 정도?

혹여 이해가지 않는 부분이 있다면 댓글 달아주시라. 그럼 필자가 최대한 빠르게 답변드리겠다.