[백준 / JAVA] 10799. 쇠막대기

https://www.acmicpc.net/problem/10799

10799번: 쇠막대기

 

---

💻 풀이 결과

 

💯 최종 코드

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String str = br.readLine();
		Stack<Character> stack = new Stack<>();
		int curr = 0;
		int cnt = 0;
		for (int i = 0; i < str.length(); i++) {
			switch (str.charAt(i)) {
			case '(':
				// 삽입한다.
				stack.push('(');

				// 그 다음꺼까지 봐야한다!!
				// 이 판단으로 레이저인지, 시작하는 조각인지를 판단해야할 것 같다.
				// 레이저라면 그냥 넘어가면 된다.
				if (str.charAt(i + 1) == '(') {
					curr++;
				}

				break;

			case ')':
				// 레이저를 쏜 것이므로 현재 가지고 있는 막대기수만큼 조각에 더해준다.
				if (stack.peek() == '(') {
					cnt += curr;
				}
				// 잘려나간 조각수 +1
				// 현재 막대기수를 -1
				else {
					cnt++;
					curr--;
				}
				
				// 삽입한다.
				stack.push(')');

				break;
			}
		}
		
		// 조각 수 출력
		System.out.println(cnt);
	}
}

 

💬 풀이 과정

• 여는 괄호를 만났을 때 스택에 삽입을 한다.
• 삽입 시에는 다음 괄호까지 보고 삽입한 괄호가 여는 괄호인지, 막대기의 시작인지 판단해야 한다.
• 막대기의 시작이라면 현재 막대기 수를 저장하는 curr의 수를 증가시킨다.
• 닫는 괄호를 만났을 때 스택의 top을 확인하고 삽입한다.
  • 스택의 top이 여는 괄호라면 레이저에 해당하므로 현재 막대기 수인 curr 만큼 조각 수 cnt에 저장한다.
  • 스택의 top이 닫는 괄호라면 막대기의 끝에 해당하므로 조각 수 cnt의 수를 증가시키고 현재 막대기 수인 curr은 감소시킨다.

💡 깨달은 점

1. 스택의 활용

• 문제를 틀리지는 않았지만, 로직을 생각하는 데에 많은 시간이 걸렸다.
• 스택을 활용하는 문제들이 비슷해 보이면서도 조금씩 생각하는 게 달라서 예외를 잘 생각하면서 로직을 짜야할 것 같다.