[백준 25918] 북극곰은 괄호를 찢어 [Java]

문제

http://boj.ma/25918

25918번: 북극곰은 괄호를 찢어

 

---

풀이

문제 요약

괄호로 이루어진 문자열을 만들기 위해 몇 번에 걸쳐 O와 X를 놓아야 하는지 계산하자.

아이디어

O 또는 X는 결국 ‘( )’ 또는 ‘) (’가 된다. 즉 어떤 괄호에 대해 이전 괄호와 같지 않다면 한 번에 놓을 수 있다.

스택에 괄호를 쌓으며, 가장 큰 스택의 크기를 출력하자. 만약 스택에 괄호가 남았다면 원하는 문자열을 만들 수 없으니 -1을 출력하자.

		// Solve
		List<Character> stack = new ArrayList<>();
		int cnt = 0;
		for (char ch : S) {
			if (stack.isEmpty() || stack.get(stack.size() - 1) == ch) {
				stack.add(ch);
				cnt = Math.max(cnt, stack.size());
			} else {
				stack.remove(stack.size() - 1);
			}
		}

풀이 시간

10분

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/easy/25918.java

problem-solving/baekjoon-online-judge/easy/25918.java at main · rogi-rogi/problem-solving