[BaekJoon] #10799 - 쇠막대기 [Java][C++]

문제 링크

---

1. 아이디어

레이저가 절단한 후 조각의 총 개수를 구해야 하는 문제로 스택 자료구조를 활용하면 해결할 수 있다. 레이저는 현재 레이저보다 먼저 등장했으면서 아직 끝이 안 나온 막대를 자르며 잘랐을 때 생기는 새로운 조각은 막대의 수와 동일하다. 막대의 경우 자신보다 긴 막대만 위에 놓일 수 있으므로 최근에 넣은 막대가 먼저 빠지게 된다.

스택에서는 열린 괄호면 일단 스택에 넣고 닫힌 괄호가 등장하면 이전이 열린 괄호인지 닫힌 괄호인지 판단하면 되는데 열린 괄호면 현재 닫힌 괄호로 레이저가 되므로 스택의 크기로 조각의 수를 세면 된다. 이때 열린 괄호와 닫힌 괄호의 쌍이 레이저가 돼서 스택에서 열린 괄호 하나를 빼고 개수를 세야 한다. 이전이 닫힌 괄호면 현재의 닫힌 괄호는 막대의 끝이므로 개수를 하나 세면 된다. 이는 레이저가 어떤 막대를 $k$번 지나가면 그 막대가 $k + 1$개의 조각이 되는데, 레이저를 만날 때마다 그 막대의 조각을 하나씩 세었으므로 막대가 끝날 때 마지막 한 조각만 더 세면 되기 때문이다.

예제 입력 2의 경우 아래와 같이 24조각이 나온다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N)$	$O(N)$

($N$ = s의 길이)

---

3. 코드

풀이 [Java][C++]

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

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

        Deque<Character> stack = new ArrayDeque<>();
        int cnt = 0;

        String s = br.readLine();
        char prv = '\u0000';

        for (char c : s.toCharArray()) {
            if (c == '(') {
                stack.push(c);
            } else {
                if (prv == '(') {
                    stack.pop();
                    cnt += stack.size();
                } else {
                    stack.pop();
                    cnt++;
                }
            }

            prv = c;
        }

        System.out.println(cnt);
    }
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    stack<char> st;
    int cnt = 0;

    string s;
    cin >> s;
    char prv = '\0';

    for (char c : s) {
        if (c == '(') {
            st.push(c);
        } else {
            if (prv == '(') {
                st.pop();
                cnt += st.size();
            } else {
                st.pop();
                cnt++;
            }
        }

        prv = c;
    }

    cout << cnt;
}

---