Stack과 Queue BOJ 10845, 9012, 4949

https://www.acmicpc.net/problem/9012

9012번: 괄호

https://www.acmicpc.net/problem/4949

4949번: 균형잡힌 세상

https://www.acmicpc.net/problem/10845

10845번: 큐

근래에 코딩 스터디에 들어가 월요일마다 공부를 하고있다. 
이번에 스택과 큐와 관련된 문제를 풀어보았다. 
이 세문제 말고도 더 있었지만.. 어려워서 못 풀었다..ㅎ

첫번째는 9012 예전에 풀었던 문제였다.

옛날에 교수님 연구실에서 공부하던 기억이 났다.

그때는 직접 구현은 해보지는 않았지만.. stack 을 써야한다는건 알고 접근할 수 있었다.

#include<iostream>
#include<stack>

using namespace std;

int t, n;
string vps;

int main() {
	cin >> t;
	for (int k = 0; k < t; k++) {
		stack<char>vp;
		n = 0;
		cin >> vps;
		for (int i = 0; i < vps.size(); i++) {
			if (vps[i] == '(') {
				vp.push(vps[i]);
			}
			else {
				if (!vp.empty()) {
					vp.pop();
				}
				else if (vp.empty() && vps[i] == ')')
					n = 1;
			}
		}
		if (vp.empty() && n != 1) {
			cout << "YES" << "\n";
		}
		else if (n == 1 || !vp.empty()) {
			cout << "NO" << "\n";
		}
	}
}

처음엔 어떻게 열린괄호와 닫힌괄호의 짝을 맞출 수 있을까 하는 생각에 많이 헤맸다..

이 문제는 열린 괄호를 만나면 stack에 넣어주고 닫힌괄호를 만나면 stack의 가장 위의 값을 pop해준다.

하지만 stack이 비어있는데 pop을 하면 에러가 나기 때문에 조심해줘야한다.

stack이 비어있지 않은데 닫힌 괄호는 pop을 해준다.

비어있는데 닫힌괄호를 만나면 n의 값을 1로 바꿔준다. 

 

stack의 마지막까지 비어있고 n의 값이 1이 아니면 yes 아니라면 no를 출력해 괄호의 짝을 확인할 수 있다.

 

다음은 4949이다.

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

int main() {

	while (1) {
		getline(cin, str);
		stack<char>st;

		if (str == ".") break;
		for (int i = 0; i < str.size(); i++) {
			if (st.empty()) {
				if ( str[i] == ']' || str[i] == ')') {
					st.push('-1');
				}
			}
			if ( str[i] == '[' || str[i] == '(') {
				st.push(str[i]);
			}

			if (str[i] == ']') {
				if (st.top() == '[') {
					st.pop();
				}
			}
			if (str[i] == ')') {
				if (st.top() == '(') {
					st.pop();
				}
			}
		}
		if (st.empty()) {
			cout << "yes"<<"\n";
		}
		else  {
			cout << "no"<<"\n";
		}
	}
}

 

먼저 틀린 코드부터 보겠다.

일단 문제점은 top이 ] , )의 짝이 아닐 때는 어떻게 하는지 선언이 안되어있다.

만약 입력이 )일 때 top이 ( 이 아닐 경우는 어떻게 할지가 없다. 

 

 

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

int main() {

	while (1) {
		getline(cin, str);
		stack<char>st;

		if (str == ".") break;
		for (int i = 0; i < str.size(); i++) {
			if (st.empty()) {
				if ( str[i] == ']' || str[i] == ')') {
					st.push('-1');
				}
			}
			if ( str[i] == '[' || str[i] == '(') {
				st.push(str[i]);
			}

			if (str[i] == ']') {
				if (st.top() == '[') {
					st.pop();
				}
				else
					st.push('-1');
			}
			if (str[i] == ')') {
				if (st.top() == '(') {
					st.pop();
				}
			else
				st.push('-1');
			}
		}
		if (st.empty()) {
			cout << "yes"<<"\n";
		}
		else  {
			cout << "no"<<"\n";
		}
	}
}

위의 틀린 코드의 문제를 해결하기 위해 ) 나 ]를 입력 받았을 때 ( 나 [ 가 아닐  때 어떻게 할지 명시해주었다.

 

마지막은 10845이다.

위의 문제들은 stack으로 풀었었다. 

이 문제는 queue로 푼 문제이다.

 

#include<iostream>
#include<queue>

using namespace std;
queue<int> q;

int main() {

	cin.tie(0);
	cin.sync_with_stdio(0);
    
	int n = 0;
	cin >> n;
	for (int i = 0; i < n; i++) {
		string a = "";
		int s=0;
		cin >> a;
		
		if (a == "push") {
			cin >> s;
			q.push(s);
		}
		else if (a == "pop") {
			if (q.empty()) {
				cout << "-1" << "\n";
			}
			else {
				
				cout << q.front() << "\n";
				q.pop();
			}
		}
		else if (a == "front") {
			if (q.empty()) {
				cout << "-1" << "\n";
			}
			else { 
				cout << q.front() << "\n"; 
			}
		}
		else if (a == "back") {
			if (q.empty()) {
				cout << "-1" << "\n";
			}
			else { 
				cout << q.back() << "\n"; 
			}
		}
		else if (a == "size") {
			cout << q.size() << "\n";
		}
		else if (a == "empty") {
			cout << q.empty()<<"\n";
		}
	
	}

}

옛날이라면 push 5를 어떻게 받아야할지 고민을 많이 했을 것 같다. 하지만 지금은 하지 않는다.ㅋ 

어려운 문제는 아니라 쉽게 풀 수 있을 거라 생각했는데 

이 마지막 -1을 출력하라는 문장을 간과하여 틀렸다.

cin.tie(0)등을 써주지 않았을 때와 썼을 때의 차이

46초 전에 제출한 코드는 cin.tie(0); cin.sync_with_stdio(0); 를 써주지 않았다. 

8초전에 제출한 코드는 위의 코드들을 작성한 후 제출했는데 이렇게 차이가 날지 몰랐다..

대단한  코드 두줄이었다.