(3) [C++, Java, Python] 백준 No.10799 : 쇠막대기

문제

풀이

 

# C++(내가 푼 방법)

- 가장 간단한 입력을 통해 생각을 해보자. ex) ( ( ) ) = 2개, ( ( ) ( ) ) = 3개

- 이것들은 어떻게 계산될 수 있을까?
- '(' 이면 스택에 넣고 
- '( )' 레이저가 나오면 스택에서 '('를 하나 빼고 스택에 있는 원소의 개수를 정답에 더한다.
- ')'가 나오면 스택에서 '('를 하나 빼고 정답에 1을 더한다.

#include <iostream>
#include <stack>

using namespace std;

int calculateAnswer(string str)
{
    int answer = 0;
    stack<char> st;

    for (int i = 0; i < str.size(); i++)
    {
        if (str[i] == '(')              //막대의 시작인 경우
            st.push('(');

        else if (str[i] == ')')
        {
            if (str[i - 1] == '('){     // 레이저인 경우
                st.pop();
                answer += st.size();
            }
            else if (str[i - 1] == ')') // 막대의 끝인 경우
            {
                st.pop();
                answer += 1;
            }
        }
    }
    return answer;
}

int main(void)
{
    ios::sync_with_stdio(false);

    string str;
    cin >> str;
    cout << calculateAnswer(str) << endl;
}

# C++(백준)

- 스택에는 어차피 '(' 만 들어가기 떄문에 문자의 인덱스를 집어넣고, 레이저를 인덱스 차로 인식하였다.

#include <iostream>
#include <string>
#include <stack>
using namespace std;
int main() {
    string a;
    cin >> a;
    int n = a.size();
    stack<int> s;
    int ans = 0;
    for (int i=0; i<n; i++) {
        if (a[i] == '(') {
            s.push(i);
        } else {
            if (s.top()+1 == i) {
                s.pop();
                ans += s.size();
            } else {
                s.pop();
                ans += 1;
            }
        }
    }
    cout << ans << '\n';
    return 0;
}

# Java

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        String a = sc.nextLine().trim();
        int n = a.length();
        Stack<Integer> s = new Stack<Integer>();
        int ans = 0;
        for (int i=0; i<n; i++) {
            char c = a.charAt(i);
            if (c == '(') {
                s.push(i);
            } else {
                if (s.peek()+1 == i) {
                    s.pop();
                    ans += s.size();
                } else {
                    s.pop();
                    ans += 1;
                }
            }
        }
        System.out.println(ans);
    }
}

# Python

import sys
r = lambda: sys.stdin.readline().strip()
s = r()
stack = []
ans = 0
for (i,c) in enumerate(s):
    if c == '(':
        stack.append(i)
    else:
        if stack[-1]+1 == i:
            stack.pop()
            ans += len(stack)
        else:
            stack.pop()
            ans += 1
print ans