스택을 이용하는 문제
내 풀이
#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;
}
'PS 연습' 카테고리의 다른 글
[자료구조] 백준 문제 풀이 - 1158 요세푸스 문제 (0) | 2022.04.10 |
---|---|
[자료구조] 백준 문제 풀이 - 1406 에디터 (0) | 2022.04.09 |
[자료구조] 백준 문제 풀이 - 1874 스택수열 (0) | 2022.04.05 |
[자료구조] 백준 문제 풀이 - 9012 괄호 (0) | 2022.04.02 |
[자료구조] 백준 문제 풀이 - 2605 줄 세우기 (0) | 2022.04.02 |