[BOJ] 10799번 쇠 막대기 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

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

public class Main {

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

        String s = br.readLine();
        Stack<Character> stack = new Stack<>();
        int sum = 0;

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            // 여는 괄호인 경우 스택에 넣고 다음 문자 확인
            if (c == '(') {
                stack.push(c);
                continue;
            }

            // 여는 괄호가 아닌 경우는 닫는 괄호 밖에 없음 -> 스택에서 꺼냄
            stack.pop();
            // 바로 직전문자가 여는 괄호 -> 레이저 -> 스택 크기 만큼 증가
            // 바로 직전 문자가 여는 괄호가 아니면 막대의 끝 -> 1 증가
            if (s.charAt(i - 1) == '(') {
                sum += stack.size();
            } else {
                sum++;
            }
        }

        System.out.println(sum);
    }
}

📄 해설

접근

• 스택을 사용하는 문제. 괄호 짝 맞추기 문제의 응용, 심화 버전이라고 보면 된다.
• 문자열을 탐색하면서 현재 문자가 여는 괄호인 경우, 스택에 넣고 닫는 괄호인 경우 필요한 처리를 해주면 된다.
• 이 문제에서는 닫는 괄호의 경우 해당 괄호가 레이저를 나타내는 괄호냐 쇠 막대기의 끝이냐를 구별해야하는데, 이는 바로 직전 문자가 여는 괄호인지 아닌지를 판별하면 된다.
• 쇠 막대기인 경우와 레이저인 경우의 처리를 다르게 해주어서 최종적으로 잘려지는 쇠 막대기 조각들의 총합을 구하면 된다.

과정

• 문자열을 입력 받고, 입력 받은 문자열의 문자를 하나씩 확인하면서 아래 과정을 수행한다.
  • 현재 문자가 여는 괄호인 경우 스택에 넣고 다음 문자를 확인한다. 이 문제의 경우 여는 괄호가 아닌 경우는 무조건 닫는 괄호이므로, continue 를 통해 다음 문자로 이동한다.
  • 현재 문자가 여는 괄호가 아닌 경우 무조건 닫는 괄호이므로, 스택에서 문자를 꺼낸다.
  • 현재 문자가 닫는 괄호이고, 바로 직전 문자가 여는 괄호라면 레이저이므로, 스택의 크기 만큼 sum 에 더해준다.
  • 직전 문자가 여는 괄호가 아니라면, 쇠 막대기의 끝이므로, sum 을 1만큼 증가시켜준다.
• sum 을 출력한다.