[BOJ] 스택(Stack)- 10828,1874,2504,4889,1918,6198 - 컴도리돌이

---

• 데이터를 일시적으로 저장하기 위해 사용하는 자료구조이며, 입출력 순서는 후입 선출(LIFO - List-in, First-out) 방식을 따른다.
• stack 클래스를 더욱 효과적으로 사용하기 위해 백준에 있는 스택 문제를 풀 생각이다.

---

std:stack

void push(int e)	e(정수형)을 맨 위에 추가
int pop()	비어있지 않으면 맨 위에 있는 요소를 삭제하고 반환
void display()	모든 요소들을 출력
int peek()	비어있지 않으면 맨 위에 있는 요소를 삭제하지 않고 반환
int size()	요소들의 개수를 반환
bool isEmpty()	비어있으면 true 아니면 false를 반환
bool isFull()	가득 차 있으면 true 아니면 false를 반환

---

10828번: 스택

• std:stack을 연습하기 좋은 기초적인 스택 문제이다.
• 필자는 이 문제를 제공되어 있는 테스트 케이스가 가볍게 풀어서 제출했지만, segment fault가 떴다. 그 이유는 스택이 비어있는지 확인을 안 하고 pop()을 해주어서 수많은 테스트 케이스에서 비어있는 arr에 pop()을 하여 오류가 뜬 거 같다.
• 스택에서 자주 하는 실수는 비어있는 스택에 pop()을 할 때 생기는 거 같다.

#include<iostream> #include<stack> #include<string> using namespace std; int main(void) { ios_base :: sync_with_stdio(false); cin.tie(NULL); cin.tie(NULL); string operation; stack<int> arr; int input_value,testcase; cin >> testcase; for(int i = 0; i<testcase; i++) { cin >> operation; if(operation == "push") { cin >> input_value; arr.push(input_value); } else if(operation == "top") { if(arr.empty() == true) { cout << -1 << "\n"; } else if(arr.empty() == false) { cout << arr.top() << "\n"; } } else if(operation == "size") { cout << arr.size() << "\n"; } else if(operation == "pop") { if(arr.empty() == true) { cout << -1 << "\n"; } else if(arr.empty() == false) { cout << arr.top() << "\n"; arr.pop(); } } else if(operation == "empty") { if(arr.empty()== true) { cout << 1 << "\n"; } else { cout << 0 << "\n"; } } } return 0; }

---

1874번: 스택 수열

#include<iostream> #include<stack> #include<string> #include<vector> using namespace std; int main(void) { ios_base :: sync_with_stdio(false); cin.tie(NULL); cin.tie(NULL); stack<int> arr1; vector<string> output; int testcase,number,min =0, index = 1; cin >> testcase; for(int i = 0; i < testcase; i++) { cin >> number; if(number >= index) { for(;index <= number;index++) { arr1.push(index); output.push_back("+"); min = arr1.top(); } } if(number < index) { if(arr1.empty() == true || arr1.top()<number ) { output.clear(); break; } for(int i=arr1.top();i>number;i--) { if(arr1.empty() == false) { arr1.pop(); } else { cout << "NO"; return 0; } } } if(number == arr1.top()) { if(arr1.empty() == false) { arr1.pop(); output.push_back("-"); } } } if(output.size() == 0) { cout << "NO"; } else { for(int i=0; i< output.size(); i++) { cout << output[i] << "\n"; } } return 0; }

---

2504번: 괄호의 값

#include<iostream> #include<stack> #include<string> using namespace std; int main(void) { string input_string; cin >> input_string; stack<char> stack_arr; int score =0,tmp = 1; for(int i=0; i< input_string.length() ; i++) { if(input_string[i] == '(' or input_string[i] == '[') { if(input_string[i] == '(') tmp *= 2; if(input_string[i] == '[') tmp *= 3; stack_arr.push(input_string[i]); } else if(input_string[i] == ')') { if(stack_arr.empty()) { cout << 0 << "\n"; return 0; } if(stack_arr.top() == '(') { if(input_string[i-1] == '(') score += tmp; stack_arr.pop(); tmp/=2; } else { cout << 0 << "\n"; return 0; } } else if(input_string[i] == ']') { if( stack_arr.empty()) { cout << 0 << "\n"; return 0; } if(stack_arr.top() == '[') { if(input_string[i-1] == '[') score += tmp; stack_arr.pop(); tmp/=3; } else { cout << 0 << "\n"; return 0; } } } if(!stack_arr.empty()) { cout << 0 << "\n"; return 0; } cout << score << "\n"; return 0; }

---

4889번: 안정적인 문자열

#include<iostream> #include<stack> #include<string> using namespace std; int main(void) { string input; int number = 1; while(1) { cin >> input; int count = 0; if(input[0] == '-') { return 0; } stack<char> arr; for(int i=0; i<input.length(); i++) { if(input[i] == '{') { arr.push(input[i]); } if(input[i] == '}') { if(arr.empty()) { arr.push('{'); count++; } else { arr.pop(); } } } if(!arr.empty()) { count = count + (arr.size()/2) ; } cout << number << ". " << count << "\n"; number++; } }

---

1918번: 후위 표기식

#include<iostream> #include<stack> #include<string> using namespace std; int main(void) { string input_string; string output_string; cin >> input_string; stack<char> temp_stack; for(int i=0; i<input_string.size(); i++) { if(input_string[i] >= 'A' && input_string[i] <= 'Z') { output_string.push_back(input_string[i]); } else { if(input_string[i] == '(') { temp_stack.push(input_string[i]); } else if( input_string[i] == '*' or input_string[i] == '/' ) { while(!temp_stack.empty() and (temp_stack.top() == '*' or temp_stack.top()== '/')) { output_string.push_back(temp_stack.top()); temp_stack.pop(); } temp_stack.push(input_string[i]); } else if(input_string[i] == '+' or input_string[i] == '-' ) { while(!temp_stack.empty() and temp_stack.top() != '(') { output_string.push_back(temp_stack.top()); temp_stack.pop(); } temp_stack.push(input_string[i]); } else if(input_string[i] == ')') { while(!temp_stack.empty() and temp_stack.top() != '(') { output_string.push_back(temp_stack.top()); temp_stack.pop(); } temp_stack.pop(); } } } while(!temp_stack.empty()) { output_string.push_back(temp_stack.top()); temp_stack.pop(); } cout << output_string; return 0; }

---

6198번: 옥상 정원 꾸미기

• Monotone stack은 말 그대로 stack을 monotone, 즉 단조롭게 하는 것 이다.
• 단조롭다는 것은 원소들이 증가하거나 감소하는 방향으로 존재하는 형태이다.
• 쉽게 얘기해서 원소들을 특정 원소를 제거해서 정렬하는 방식이다.

#include<iostream> #include<stack> #include<vector> using namespace std; int main(void) { int testcase_N = 0,value = 0; long long building_score =0; //long long 으로 안해주면 error 발생 cin >> testcase_N; vector<int> arr; stack<int> monotone_stack; for(int i = 0; i<testcase_N ; i++) { cin>> value; arr.push_back(value); } for(int i =0; i<testcase_N ; i++) //monotone stack 알고리즘 { while(!monotone_stack.empty() and monotone_stack.top() <= arr[i]) { monotone_stack.pop(); } monotone_stack.push(arr[i]); building_score += monotone_stack.size() - 1; } cout << building_score; return 0; }