백준 1541 - 잃어버린 괄호 JAVA

단계별로 풀기의 동적 계획법 1이 끝나고 맞이하는 그리디 알고리즘이다.

프로그래머스의 그리디 알고리즘 보면 난이도가 ㅎㄷㄷ하다.

그냥 뭔지 모를 때 거시기,, 그거 그거 있잖여 그리디 이거 그리디여라~라고 하면 다 그리디다 ㅠㅠ

문제, 입출력, 테스트케이스

해당 문제는 그리디라는 걸 이미 알고 풀어서 그런지 애초에 그리디하게 접근을 하였다. 문제 접하고 한 5분간 테케 1번이 왜 -35이지?라고 의문이 들었던 흑웁니다.. ㅜㅜ

 

<문제 접근/풀이과정>
1. 2, 3번 테케? 그럴 수 있지. 1번은 뭐지??
2. 아! A-(B+C) 이런 식으로 괄호를 친거구나
3. 그렇다면 -가 나온 뒤에는 무조건 빼주면되지 않을까?
4. A-B+C+D-E+F = A-(B+C+D)-(E+F)가 되니까 그냥 -가 나온 뒤로는 빼준다고 생각하면 되겠다!
5. EZ해~
6. 엌... 문자열 슬라이싱까지 해야하잖아? substring을 써야겠다! 
7. 그리고 Integer.parseInt를 하면 String의 "000X" -> X로 바뀌니까 앞에 0 붙는 건 신경쓰지 말아야겠다.

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) {
		// 양수, +, -, 괄호
		// 괄호를 적당히 쳐서 최소로 만드는 경우
		// -가 나오면 그 뒤에부터 그다음 -가 나올 때 까지 합한 수를 빼기
		Scanner sc = new Scanner(System.in);
		String str = sc.next();
		String dividedStr[] = new String[50];
		int index = 0;
		int cursor = 0;
		for (int i = 0; i < str.length(); i++) { // 숫자와 연산자 슬라이싱 문자열 만들기
			if (str.charAt(i) == '+' || str.charAt(i) == '-') { 
				dividedStr[index++] = str.substring(cursor, i);
				dividedStr[index++] = str.substring(i, i + 1);
				cursor = i + 1;
			} else if (i == str.length() - 1) {
				dividedStr[index++] = str.substring(cursor, str.length());
			}
		}
		boolean plusOrMinus = false;
		int answer = 0;
		for (int i = 0; i < index; i++) {
			if (dividedStr[i].equals("+")) { // +가 나온다면 그냥 continue
				continue;
			} else if (dividedStr[i].equals("-")) { // -가 나온다면 즉시 뒤의 숫자 빼기로 전환
				plusOrMinus = true;
				continue;
			}

			if (!plusOrMinus) { // -연산자를 한 번이라도 만났니?
				answer += Integer.parseInt(dividedStr[i]); // 안 만났으면 더해
			} else {
				answer -= Integer.parseInt(dividedStr[i]); // 만났으면 빼
			}
		}
		System.out.println(answer);

	}
}

사실상 테케 1번이 좋은 힌트였다.

동적계획법 1을 벗어나니 뭔가 숨통이 트인 느낌이다(라고 할 뻔)