C++ 자료구조 1 - 스택(stack)/백준 9093번, 9012번

Stack(스택)은 한쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조이다.

마지막으로 넣은 것이 가장 먼저 나오기 때문에 last in first out (LIFO)라고도 한다.

 

stack의 기본적인 기능은

push: 스택에 자료를 넣는 연산

pop: 스택에서 자료를 빼는 연산

top: 스택의 가장 위에 있는 자료를 보는 연산

empty: 스택이 비어있는지 아닌지를 알아보는 연산

size: 스택에 저장되어있는 자료의 개수 를 알아보는 연산

 

스택은 밑이 막혀있는 그릇 같은?? 구조라고 보면 되는데 우리가 먼저 넣은 음식이 맨 밑에 깔리는 거랑 같다고 보면 된다.

그래서 1 2 3 4 5 를 차례대로 스택 안에 넣었다고 가정하면

가장 먼저들어간 1이 가장 밑에 깔리고 제일 늦게 들어간 5가 스택의 맨 위에 있다.

 

그림으로 그려보면

 

 

이렇게 스택에 차곡차곡 쌓여있다고 볼 수 있다!!

 

그래서 여기서 top()을 호출하면 가장 위에 있는 5를 리턴하고

pop()을 호출하면 가장 위에 있는 5가 삭제된다.

 

5를 삭제(pop)한 뒤에 push(6)을 하면 4 위에 6이 쌓인다.

그 뒤에 size()를 호출하면 1 2 3 4 6 이 들어있기 때문에 5가 리턴이 될 것이다.

 

이 stack을 문제 푸는 것에 활용해보자!!!!

 

백준 9093번 www.acmicpc.net/problem/9093

9093번: 단어 뒤집기

단어들은 띄어쓰기로 구분된다. i am student라는 문장을 입력하면 단어 뒤집기가 돼서

i ma tneduts로 출력된다.

여기서 스택의 LIFO특성을 생각해볼 수 있는데 처음에 말했듯이 스택은 먼저 들어간 친구가 가장 마지막에 나온다는 특성이 있다.

그래서 여기서 알파벳 하나씩 차곡차곡 스택에 쌓고 띄어쓰기가 입력되면 단어가 끝이 난 것이니까 차례대로 꺼내면 단어가 뒤집어진다는 것을 알 수 있다.

 

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

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int t;
	cin >> t;
	cin.ignore(); //얘는 버퍼 전체를 비우는 것이 아니라 맨 앞의 문자 하나만 지운다. 이걸 쓴 이유는 cin은 \n을 입력받지 않음으로 cin에서 t를 입력받고 엔터를 친게 그대로 getline에 들어가서 \n을 지워줄려고 넣은것!!  
	while (t--) {
		string str;
		getline(cin, str); // '\n'이 들어올때 까지 입력 받는다.
		str += '\n'; // 맨뒤에 \n 추가해준다 왜냐면 우리는 단어들을 띄어쓰기로 구분할꺼니까.
		
		stack<char> s;
		for (char ch : str) { //str의 문자 하나씩 스택에 넣어주기 위해서 for문 사용
			if (ch == ' ' || ch == '\n') {
				while (!s.empty()) {
					cout << s.top();
					s.pop(); //꺼낸 친구는 삭제시키자
				}
				cout << ch; //띄어쓰기 해주기
			}
			else {
				s.push(ch);
			}
		}
	}
	return 0;
}

 

백준 9012번 www.acmicpc.net/problem/9012

9012번: 괄호

괄호 문자열이 주어졌을 때, 올바른 괄호 문자열인지 아닌지를 알아보는 문제이다.

여기서 올바른 괄호 문자열이란 괄호의 쌍이 올바른 문자열을 말한다.

((())) , ()(()) 같은 애들이 올바른 괄호 문자열이다.

 

여기서 괄호 쌍의 특성을 알아야 하는데 먼저 닫는 괄호 앞에 쌍을 이루지 않는 여는 괄호가 있어야 하고 이 쌍을 이루지 않는 여는 괄호 중 가장 가까운 괄호가 쌍을 이루게 된다.

이게 무슨 뜻이냐면

((())) 이런 괄호가 있으면

절대 ((())) 이렇게 짝지어질 수 없다. 너무 당연한 거!!

그래서 ((())) 이 파란 괄호 앞에 아직 쌍을 이루지 않은 여는 괄호들이 3개가 있고 여기서 파란 괄호와 가장 가까운 괄호가 쌍을 이루게 된다. ((())) 이렇게 쌍을 이루게 된다는 뜻

 

이 특성을 이해해서 우리는 여는 괄호들을 스택에 넣고 닫는 괄호를 만나면 이 여는 괄호 스택에서 가장 위에 있는(가장 최근에 push 된) 여는 괄호를 데려와서(pop) 닫는 괄호와 짝을 지어주면 되고 또 여는 괄호를 만나면 또 차곡차곡 스택에 쌓고 닫는 괄호를 만나면 또 이 스택에서 가장 위에 있는 괄호를 데려오고를 반복하다가 문자열이 끝났을 때 여는 괄호 stack이 비어있으면 된다!!!!

 

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

using namespace std;

string valid(string s) {
	int cnt = 0;
	stack<char> st;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == '(') {
			st.push(s[i]);
		}
		else {
			if (!st.empty())
				st.pop(); // 닫는괄호면 여는괄호 스택의 제일 최근에 들어온 여는괄호 pop!! 근데 스택이 비었으면 올바른 괄호 문자열이 아닌거
			else return "NO";
		}
	}
	if (st.empty()) return "YES"; //문자열이 끝났을때 스택이 비었으면 올바른 괄호 문자열
	else return "NO"; //아니면 올바르지 않은 문자열
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int t;
	cin >> t;
	while (t--) {
		string s;
		cin >> s;
		cout << valid(s) << '\n';
	}
	return 0;
}