[백준 1541번] 잃어버린 괄호 - 쉽고 간단한 풀이

www.acmicpc.net/problem/1541

1541번: 잃어버린 괄호

 

이 문제는 어려운 문제는 아니지만 재밌는 요소가 있습니다.

 

가장 맨 위 A-B+C+D-E 의 예를 보시면 - 부호 다음으로 괄호를 열고 - 부호 이전까지 괄호를 닫는 식으로 마이너스 항들을 괄호로 확장해가면서 식의 결과값을 최소화 할 수 있습니다.

 

이를 바로 구현하기 전에 그 바로 아래를 살펴보시죵 ㅎㅎㅎ

 

만약 a번째 항 바로 앞에서 마이너스 부호가 최초로 나타났다고 가정합니다. (그전까지는 숫자항들을 모두 더했겠죠?)

그리고 n번째 항 앞의 부호가 마이너스 일때와 플러스 일때 둘 다를 살펴보면 재밌는 사실을 발견할 수 있습니다.

 

플러스 일땐 마이너스 괄호를 확장합니다. 결국 totalSum 이라는 변수가 총합을 나타낸다면 totalSum에서 빼주게 됩니다.

마이너스 일때는 그 앞의 괄호를 닫습니다. 그리고 마지막 항이 아니라면 새로운 마이너스 괄호를 열게 됩니다. 결국! totalSum에서 빼주는 같은 결과를 나타냅니다.

 

이 사실이 말해주는 결론은 무엇일까요? 

그 것 은 마이너스가 최초로 나타나는 시점 이후의 항들은 전부 빼주면 답이 된다는 사실!

 

재밌지 않나요? ㅋㅋㅋ

 

 

아래는 코드입니다

..

/*
백준 1541번 - 잃어버린 괄호
 */
public class Main {
	public static void main(String[] args) throws IOException {
//		InputReader reader = new InputReader("testcase.txt");
		InputReader reader = new InputReader("testcase.txt");
		String input = reader.readLine();

		List<String> terms = split(input);
		int min = solve(terms);
		System.out.println(min);
	}

	private static List<String> split(String input) {
		Pattern pattern = Pattern.compile("[0-9]+|[\\-\\+]");
		Matcher matcher = pattern.matcher(input);
		List<String> terms = new ArrayList<>();
		while(matcher.find()) {
			terms.add(matcher.group());
		}
		return terms;
	}

	private static int solve(List<String> terms) {
		int totalSum = Integer.parseInt(terms.get(0));
		boolean minusFlag = false;
		for (int i = 1; i < terms.size(); i++) {
			String term = terms.get(i);
			
			//연산자인 경우
			if(isOperator(term) ) {
				if(term.equals("-")) minusFlag = true;
				continue;
			}
			//숫자인 경우
			int termVal = Integer.parseInt(term);
			if(minusFlag) {
				totalSum -= termVal;
			}else {
				totalSum += termVal;
			}
			
		}
		return totalSum;
	}

	public static boolean isOperator(String term) {
		if(term.equals("+") || term.equals("-")) return true;
		return false;
	}
}
class InputReader {
	private BufferedReader br;

	public InputReader() {
		br = new BufferedReader(new InputStreamReader(System.in));
	}

	public InputReader(String filepath) {
		try {
			br = new BufferedReader(new FileReader(filepath));
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
	}

	public String readLine() throws IOException {
		return br.readLine();
	}
	public int readInt() throws IOException {
		return Integer.parseInt(readLine());
	}
}

.