[자료구조] 백준 문제 풀이 - 10799 쇠막대

 

스택을 이용하는 문제

 

내 풀이

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

int main()
{
	int stick_count=0;
	int result=0;
	stack <char> s;
	string stick_lazor; //stack의 top을 봐야겠네
	cin>>stick_lazor;
	
	for(int i=0; i<stick_lazor.size()-1; i++)
	{
		if(stick_lazor[i]=='(')
		{
			stick_count++;
			s.push(stick_lazor[i]);

		}
		else // )인 경우
		{
				
			if(s.top()=='(') // () 레이저
			{
				stick_count--; // 스틱인줄 알고 ++된거 다시 --로 돌리는 과정
				result+=stick_count;
				s.push(stick_lazor[i]);
			}
			else // ))
			{
				stick_count--;
				s.push(stick_lazor[i]);
				result++;
			}
		}
	}
	cout<<result+1<<endl;
}

->input[i]==')' and input[i-1]=='(' 느낌으로 i-1 사용할수 있음

 

다른 사람의 풀이 

1. 스택 안에 있는 ' ( ' 의 갯수를 선의 갯수로 봄

2. 마무리 ' ) ' 에서 total++로 원래 있던 쇠막대를 더해주고 쇠막대 끝난거니까 ' ( ' 한개를 없에줌 

#include <iostream>
#include <string>
#include <stack>


using namespace std;


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	stack<char> S;
	string input;
	int total = 0;
	cin >> input;
	for (int i = 0; i < input.length(); i++) {
		if (input[i] == '(') {
			S.push(input[i]);
		}
		else if(input[i]==')' and input[i-1]=='('){ // 레이저일때
			S.pop();
			total += S.size(); // 스택안에 있는 '('는 막대의 갯수
		}
		else { // 마지막 자투리일때
			total++; // 쇠막대 1개치 더해줌
			S.pop(); // 겹쳐있는 쇠막대 1개 없어짐
		}
	}
	cout << total << endl;
}