[BOJ][10799] 쇠막대기

1. 문제 링크

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

2. 사용 알고리즘

스택

3. 풀이

1. 총 막대기의 개수를 저장할 정수형 변수를 선언 후 0으로 초기화

2. 정수 값을 저장하는 스택 선언

3. 여는 괄호인 경우 문자열의 인덱스를 push

4. 닫는 괄호인 경우 스택의 top(가장 마지막으로 연 괄호) 확인

   1) 스택의 top이 현재 인덱스 - 1인 경우 : 레이저

   pop을 통해 여는 괄호 1개 제거(막대기가 아니라 레이저이므로)

   변수에 스택의 현재 사이즈(레이저로 절단했을 때 잘리는 막대기 수) 더해줌

   2) 스택의 top이 현재 인덱스 - 1이 아닌 경우 : 막대기의 끝부분

   pop을 통해 여는 괄호 1개 제거(전체 막대기 수 1개 감소)

   변수에 1을 더해줌(막대기를 2번 자르면 3개가 되므로 마지막 세 번째의 막대기를 나타냄)

4. 소스 코드

4-1. C++

https://github.com/dev-aiden/problem-solving/blob/main/boj/10799.cpp

#include <iostream>
#include <stack>

using namespace std;

stack<int> s;

int main(void) {
    ios_base::sync_with_stdio(false);
    string str; cin >> str;
    int len = str.length();
    int ans = 0;
    for (int i = 0; i < len; ++i) {
        if (str[i] == '(') {
            s.push(i);
        } else {
            if (s.top() == (i - 1)) {
                s.pop();
                ans += s.size();
            } else {
                s.pop();
                ++ans;
            }
        }
    }
    cout << ans << "\n";
    return 0;
}

4-2. JAVA

https://github.com/dev-aiden/problem-solving/blob/main/boj/10799.java

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));
        Stack<Integer> s = new Stack<>();
        String str = br.readLine();
        int len = str.length();
        int ans = 0;
        for (int i = 0; i < len; ++i) {
            if (str.charAt(i) == '(') {
                s.push(i);
            } else {
                if (s.peek() == (i - 1)) {
                    s.pop();
                    ans += s.size();
                } else {
                    s.pop();
                    ++ans;
                }
            }
        }
        System.out.println(ans);
    }
}