[백준] 10799번 쇠막대기 / C++ Java

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

C++

#include<iostream>
#include<stack>
using namespace std;

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

    stack<int> s;
    string str;
    int count = 0;
    cin >> str;

    for(int i = 0; i < str.size(); i++) {
        if(str[i] == '(' && str[i+1] == ')') {
            count += s.size();
            i += 1;
        }
        else if(str[i] == '(') {
            s.push(i);
        }
        else if(str[i] == ')') {
            count += 1;
            s.pop();
        }
    }
    cout << count << endl;
}

Java

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        Stack<Character> s = new Stack<>();
        String str = br.readLine();
        int count = 0;

        // charAt(i) 함수는 String 타입의 데이터에서 특정 문자를 char 타입으로 변환
        for(int i = 0; i < str.length(); i++) {
            if(str.charAt(i) == '(' && str.charAt(i+1) == ')') {
                count += s.size();
                i += 1;
            }
            else if(str.charAt(i) == '(') {
                s.push(str.charAt(i));
            }
            else if(str.charAt(i) == ')') {
                count += 1;
                s.pop();
            }
        }
        bw.write(count + "\n");
        bw.flush();
        br.close();
    }
}

문제풀이

• ( ) 일 경우에는 레이저를 쏘고, ( )일 경우에는 막대기를 생성한다. 생성된 막대기는 레이저를 만나면 잘라진다. 먼저 '(' 경우에는, stack에 값을 push한다. 그리고 ')' 경우에는, 가장 최근의 '('와 만나서 생성된 막대기가 잘리기 때문에 총 잘린 막대기 수를 +1 해주고, stack 안에 있는 '(' pop해준다. 마지막으로 '( )' 경우에는 그 전에 stack에 담겨있는 '(' 개수만큼 더해준다.

Comment

• 괄호 문제의 경우 스택을 사용해서 '(' 경우에는 push해주고, ')'경우에는 pop 해야한다는 것까지 알았다. 하지만 어떤 식으로 문제를 해결해야할지 감이 안잡혔다. 레이저를 쏴서 그 전에 담겨있는 스택의 개수를 센다는건 상상도 못한 방법이었다.
  참고 블로그 : https://ohsol.tistory.com/entry/%EB%B0%B1%EC%A4%80-10799%EB%B2%88-%EC%87%A0%EB%A7%89%EB%8C%80%EA%B8%B0-C-%ED%92%80%EC%9D%B4