백준 알고리즘 분류 (그리디 알고리즘)
https://www.acmicpc.net/problem/1541
# 문제
세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.
그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.
괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.
# 예제
입력 : 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.
55-50+40
출력
-35
# 필요개념
주어진 식으로 최솟값을 만들어내려면, -와 - 사이의 식을 먼저 계산해야한다. 예를들어
20 + 30 - 60 + 30 + 10 - 20 + 30 이 있다면, -뒤에있는 60 + 30 + 10 과 20 + 30 을 먼저 계산하여 20 + 30 - ( 60 + 30 + 10 ) - (20 + 30) 이런 모양의 식을 풀어내야 한다. 바꿔말하면 덧셈연산을 먼저 해야한다는 의미이다!
✅덧셈 연산을 먼저 하려면
덧셈 먼저 연산을 하기 위해서는 뺄셈 연산을 기준으로 문자열을 나누어야 한다. 위 예시 식을 뺄셈 연산을 기준으로 나눠주면 (20 + 30), (60 + 30 + 10), (20 + 30) 이렇게 나누어진다. 나누어 진 것을 +를 기준으로 쪼개어 더해주면 구할 수 있다.
문자열을 쪼갤 때는 크게 두가지 방법을 쓸 수 있다.
- String의 split() 메소드
- StringTokenizer
필자는 StringTokenizer을 이용했다. StringTokenizer에 대한 자세한 설명을 아래 링크에 기록해두었다.
https://wanna-developer02.tistory.com/71
그런데 뺄셈 기준으로 나눈 StringTokenizer중 모두 빼기 연산을 시키면 안된다. 첫 수는 양수이기 때문에 이 부분을 주의해줘야 하는데, 첫 토큰을 구별하는 방법에 대해 고민해보았다. 구글링을 해보니 첫 수를 특수한 수 (Integer.MAX_VALUE나 Integer.MIN_VALUE) 로 지정해두고, 값이 같으면 변화하지 않은 것이므로 첫번째토큰이라고 생각하는 것이다. 난 항상 for문을 사용해 i == 0 을 기준으로 했는데 이렇게 하면 while문을 활용할 때 불편했었다. 이런 방법도 있음을 알게 된 문제였다!
# Code
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer ab = new StringTokenizer(br.readLine(), "-");
int total = Integer.MIN_VALUE;
while (ab.hasMoreTokens()) {
int sum = 0;
StringTokenizer ad = new StringTokenizer(ab.nextToken(), "+");
while (ad.hasMoreTokens()) {
sum += Integer.parseInt(ad.nextToken());
}
if (total == Integer.MIN_VALUE) total = sum;
else total -= sum;
}
System.out.println(total);
}
}
# 결과
'코딩테스트 > 백준 브론즈,실버' 카테고리의 다른 글
[백준] 1654 : 랜선 자르기 (이분 탐색) - JAVA (1) | 2024.03.12 |
---|---|
[백준] 1931 : 회의실 배정 (활동선택문제) - JAVA (1) | 2024.02.18 |
[백준] 2485 : 가로수 (최대공약수, 답을 내는 방법에 대하여) - JAVA (1) | 2024.02.11 |
[백준] 4134 : 다음 소수 (Math.sqrt) - JAVA (0) | 2024.02.08 |
[백준] 10815 : 숫자 카드 (List와 Set의 Contains()) - JAVA (0) | 2024.02.02 |