[C++] 백준(BOJ) 10799 쇠막대기

와 너무 힘들었다...

스택을 활용하는 건 알겠는데, 시간이 너무 오래 걸려 인터넷에서 힌트를 얻을 수 밖에 없었다.

이 힌트를 보고

코드를 작성했다.

풀이1 (내풀이)

• 레이저 () 인 경우 / ( ( 인 경우 / ) ) 인 경우 3가지 케이스로 나누어 작성하였다
• 레이저 () 인 경우 : 
  • stack에 담긴 ( 의 개수만큼 allCount(총 막대 개수) 에 더했다
• ( ( 인 경우 :
  • stack에 ( push
• ) ) 인 경우 :
  • allCount에 1 추가후, stack의 ( 1개 pop

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

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	vector<char> pa;
	string s;


	getline(cin, s);  // 한 줄을 입력받음

	for (int i = 0; i < s.length(); i++)
	{
		pa.push_back(s[i]);
	}
	
	stack<char> ch;
	int allCount = 0;
	for (int i = 0; i < pa.size(); i++)
	{
		if (i+1 < pa.size() && pa[i] == '(' && pa[i + 1] == ')') // () 레이저
			allCount += ch.size();
		else if (i+1 < pa.size() && pa[i] == '(' && pa[i+1] == '(') // ( (인 (
			ch.push('(');
		else if (i - 1 >= 0 && pa[i - 1] == ')' && pa[i] == ')')
		{
			allCount++;
			ch.pop();
		}
	}
	cout << allCount;

	return 0;
}

 

풀이2 (다른 사람)

• 조건문을 더 간단히 한 코드로 가독성이 더 좋은 것 같다
  • (가 들어오는지, )가 들어오는지
  • )가 들어온다면,
    • 이전에 (가 들어왔는지, 이전에 )가 들어왔는지에 따라 간단하게 나누었다.
• 카운트하는 방법은 똑같다

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

int main() {
    string a;
    int cnt = 0;
    cin >> a;
    stack<int> s;		// 스택 생성
        for (int i=0; i < a.size(); i++) {		// 문자열 크기만큼 반복
            if (a[i] == '(')		// '('가 들어오면 스택에 넣는다.
                s.push(a[i]);
            else {					// ')' 가 들어오는 경우
                if (a[i-1] == '(') {	// 이전에 '('가 들어왔다면 pop하고 스택의 크기를 cnt에 더해준다.
                	s.pop();
                    cnt+=s.size();
                }
                else {			// 그렇지 않다면 pop하고 cnt에 1을 더한다.
                	s.pop();
                    cnt++;
                }
            }
        }
    cout << cnt;
    return 0;
}

---