[BOJ] 10799: 쇠막대기 (JAVA)

문제

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

 

여담

3개월 전쯤에 풀이를 참고하지 않고 풀었던 문제인데 이번에는 예전의 내 코드를 보고 풀었다... 나름 실력이 늘었다고 생각했는데 전에 풀었던 문제도 못 푸는 것 보면 그렇지 않은가 보다. 대체 코테 실력은 언제 늘까..? 너무 슬프다

 

풀이

이 문제는 현재 문자가 (인 경우와 )인 경우를 나눈 뒤, 스택을 이용해서 문제를 풀면 된다.

 

현재 문자가 (라면 다음 문자를 통해 현재 문자가 쇠막대기의 오른쪽을 뜻하는지, 레이저를 뜻하는지 판별해야 한다.

만약 다음 문자가 )라면 레이저를 뜻하므로 잘린 쇠막대기가 생기게 된다. 따라서 현재 잘린 쇠막대기의 수, 즉 스택에 담긴 수만큼 total에 더하면 된다. 

다음 문자가 (라면 쇠막대기의 오른쪽을 뜻하므로, 그냥 스택에 push하면 된다.

 

현재 문자가 )라면 쇠막대기의 오른쪽 끝을 뜻한다. 즉, 막대기가 끝이 나기 때문에 잘린 막대기가 1개 생기게 된다. 따라서 total에 1을 더하고 스택에서 pop하면 된다.

 

정리하면 다음과 같다.

• 현재 문자가 (
  • 다음 문자가 ): 레이저를 뜻하므로, 스택에 담긴 수 더하기 (total += stack.size())
  • 다음 문자가 (: 스택에 push하기
• 현재 문자가 `)`
  • total에 1을 더하고 스택에서 pop하기

 

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String pipes = br.readLine();
        int total = 0;
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < pipes.length() - 1; i++) {
            char now = pipes.charAt(i);
            if (now == '(') { // 현재 괄호가 열린 괄호라면
                char next = pipes.charAt(i + 1); // 다음 괄호 확인하기
                if (next == ')') { // 다음 괄호가 닫힌 괄호라면
                    // 레이저를 뜻하므로 잘린 파이프의 수(=스택의 크기) 더하기
                    total += stack.size();
                    i++;
                } else {
                    // 그렇지 않다면 막대기를 뜻하므로 스택에 넣기
                    stack.push(now);
                }
            } else { // 닫힌 괄호라면 파이프의 끝을 뜻하므로 1 더하기
                total++;
                stack.pop();
            }
        }
        // 편의상 pipes.length - 1까지 탐색했으므로, 마지막의 괄호(=파이프의 끝) 고려하기
        if (!stack.isEmpty()) total++;
        System.out.println(total);
    }
}

---