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

문제 링크

---

1. 아이디어

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

스택에서는 열린 괄호면 일단 스택에 넣고 닫힌 괄호가 등장하면 이전이 열린 괄호인지 닫힌 괄호인지 판단하면 되는데 열린 괄호면 현재 닫힌 괄호로 레이저가 되므로 스택의 크기로 조각의 수를 세주면 된다. 이때 열린 괄호와 닫힌 괄호의 쌍이 레이저가 되서 스택에서 열린 괄호 하나를 빼주고 개수를 세야 한다. 이전이 닫힌 괄호면 현재의 닫힌 괄호는 막대의 끝이므로 개수를 하나 세주면 된다.

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

---

2. 코드

1. 풀이 [Java]

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);
    }
}

2. 풀이 [C++]

#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;
}

---

3. 디버깅

막대기가 그냥 끝나서 개수를 세야 하는 것에 주의해야 하는데 예제 입력 2에 친절하게 나와있어서 도움이 됐다.

---

4. 참고

없음.

---