백준 알고리즘 기초 : 자료구조 (1)

Stack에 대한 문제들을 다루는 챕터이다. Queue(큐)와 Deque(덱)은 그래프와 BFS에서 집중적으로 다룰 예정이다.

https://shine-slowly.tistory.com/39

알고리즘 : 자료구조(1) 스택 (Stack) (C++로 구현)

스택을 아예 모른다면 이 글을 가볍게 읽는 것을 추천한다.

c++로 스택을 구현하는 과정과 c++ stl stack을 사용하는 방법이 나와 있다.

 

 

10828. (스택) 정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

#include<iostream>
#include<stack>
#include<string>
using namespace std;
int main() {
	stack <int> s;
	int n;
	cin >> n;
	string command;
	while (n--) {
		cin >> command;
		if (command == "push") {
			int val;
			cin >> val;
			s.push(val);
		}
		else if (command == "pop") {
			if (s.size() > 0) {
				cout << s.top() << "\n";
				s.pop();
			}
			else
				cout << -1 << "\n";
		}
		else if (command == "top") {
			if (s.size() > 0) {
				cout << s.top() << "\n";
			}
			else {
				cout << -1 << "\n";
			}
		}
		else if (command == "size") {
			cout << s.size() << "\n";
		}
		else {
			cout << s.empty() << "\n";
		}
	}
	return 0;
}

직접 구현하는 방법은 맨 위에 걸어둔 링크에 들어가면 나와있다.

 

 

 

9093. (단어 뒤집기) 문장이 주어졌을 때, 단어를 모두 뒤집어서 출력하는 프로그램을 작성하시오. 단, 단어의 순서는 바꿀 수 없다. 단어는 영어 알파벳으로만 이루어져 있다.

#include<iostream>
#include<string>
using namespace std;
int main() {
	int n;
	string str;
	cin >> n;
	cin.ignore(); // 입력 버퍼의 모든 내용 제거
	for (int i = 0; i < n; i++)
	{
		getline(cin, str);
		int temp = 0;
		for (int j = 0; j < str.length(); j++)
		{ 
			if (str[j] == ' ') {
				for (int k = j-1; k >= temp; k--)
				{
					cout << str[k];
				}
				temp = j + 1;
				cout << " ";
			}
		}
		for (int k = str.length() - 1; k >= temp; k--)
		{
			cout << str[k];
		}
		cout << "\n";
	}
	return 0;	
}

getline() 함수를 사용할 때 주의해야할 점이 있는데, getline 전에 어떤 변수를 입력받았다면 cin.ignore()로 버퍼를 비워주어야 한다는 것이다. 입력 버퍼를 지우지 않으면 엔터가 남아있어서 str에 엔터가 저장되기 때문이다.

 

#include<iostream>
#include<stack>
#include<string>
using namespace std;
int main() {
	int n;
	cin >> n;
	string sen;
	stack <char> st;
	cin.ignore();
	while (n--) {
		getline(cin, sen);
		for (int i = 0; i < sen.length(); i++)
		{
			if (sen[i] == ' ') {
				while (!st.empty()) {
					cout << st.top();
					st.pop();
				}
				cout << " ";
			}
			else {
				st.push(sen[i]);
			}
		}
		while (!st.empty()) {
			cout << st.top();
			st.pop();
		}
		cout << "\n";
	}
	return 0;	
}

이 문제는 stack 관련 문제이기 때문에 stack을 사용해서도 구현해보았다. 삼중 반복문이 사용되는 것은 동일했다.

 

 

 

9012. (괄호) 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다. 

#include<iostream>
#include<stack>
#include<string>
using namespace std;
int main() {
	int n;
	bool vps;
	cin >> n;
	string x;
	stack <char> stack;
	while (n--) {
		vps = 1;
		cin >> x;
		for (int i = 0; i < x.length(); i++)
		{
			if (x[i] == '(') {
				stack.push(x[i]);
			}
			else {
				if (!stack.empty()) {
					stack.pop();
				}
				else {
					vps = 0;
					break;
				}
			}
		}

		if (vps == 0) {
			cout << "NO\n";
		}
		else {
			if (stack.size() > 0) {
				while (!stack.empty()) {
					stack.pop();
				}
				cout << "NO\n";
			}
			else
				cout << "YES\n";
		}	
	}
	return 0;	
}

나는 stack을 while 문 밖에다 선언해서 마지막에 팝을 해주는 작업이 필요했는데 while 문 안에 선언하면 그런 과정이 필요없다.

 

 

 

1874. (스택 수열) 스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.

#include<iostream>
#include<stack>
#include<string>
#include<vector>
using namespace std;
int main() {
	int n;
	cin >> n;
	int current = 0;
	stack<int> stack;
	vector<char> v;
	for (int i = 0; i < n; i++)
	{
		int x;
		cin >> x;

		while (current < x) {
			stack.push(++current);
			v.push_back('+');
		}

		if (stack.top() == x) {
			stack.pop();
			v.push_back('-');
		}
		else {
			cout << "NO\n";
			return 0;
		}
	}
	for (int i = 0; i < v.size(); i++)
	{
		cout << v[i] << "\n";
	}
}

간단하게 구현할 수 있는 코드였다. 나는 조건 세우는 걸 잘못해서 첫번째 코드가 위 코드의 거의 2배였다 ㅠ.ㅠ

시간은 왜 더 적게 나왔는진 모르겠지만 필요없는 조건을 만드는 습관을 없애야겠다.

 

 

 

1406. (에디터) 한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다. 이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다. 이 편집기가 지원하는 명령어는 다음과 같다.

(아래는 시간초과 코드입니다. 굳이 볼 필요 없으니 그다음 코드를 봐주세요.)

#include<iostream>
#include<stack>
#include<string>
using namespace std;
int main() {
	string sentence;
	cin >> sentence;
	int m;
	cin >> m;
	int now = 0;
	stack <char> s;
	for (int i = sentence.length() - 1; i >= 0; i--)
	{
		s.push(sentence[i]);
	}

	while (m--) {
		char command;
		cin >> command;
		switch (command) {
		case 'L': {
			if (now < s.size()) {
				now++;
			}
			break;
		}
		case 'D': {
			if (now > 0) {
				now--;
			}
			break;
		}
		case 'B': {
			stack <char> temp;
			if (now == s.size())
				break;
			int repeat = s.size() - now - 1;
			while (repeat--)
			{
				temp.push(s.top());
				s.pop();
			}
			s.pop();
			while (!temp.empty())
			{
				s.push(temp.top());
				temp.pop();
			}
			break;
		}
		case 'P': {
			char x;
			cin >> x;
			stack <char> temp;
			int repeat = s.size() - now;
			while (repeat--)
			{
				temp.push(s.top());
				s.pop();
			}
			s.push(x);
			while (!temp.empty())
			{
				s.push(temp.top());
				temp.pop();
			}
			
			break;
		}
		}
	}
	while(!s.empty())
	{
		cout << s.top();
		s.pop();
	}
}

처음 짠 코드는 이와 같다. 시간초과가 뜰 걸 알고 짠 코드이긴한데 역시 시간초과가 떴다!

 

1) Stack을 이용한 구현

#include<iostream>
#include<stack>
using namespace std;
int main() {
	string sentence;
	int m;
	cin >> sentence >> m;
	stack <char> left;
	stack <char> right;
	for (int i = 0; i < sentence.length(); i++)
	{
		left.push(sentence[i]);
	}

	while (m--) {
		char command;
		cin >> command;
		switch (command) {
		case 'L': {
			if (left.empty())
				break;
			right.push(left.top());
			left.pop();
			break;
		}
		case 'D': {
			if (right.empty())
				break;
			left.push(right.top());
			right.pop();
			break;
		}
		case 'B': {
			if (left.empty())
				break;
			left.pop();
			break;
		}
		case 'P': {
			char x;
			cin >> x;
			left.push(x);
			break;
		}
		}
	}

	while (!left.empty()) {
		right.push(left.top());
		left.pop();
	}
	while (!right.empty()) {
		cout << right.top();
		right.pop();
	}
}

left, right을 나눠서 구현하라는 힌트를 보고 짰는데 진짜 너~무 간결해졌다...

 

2) List를 이용한 구현

https://shine-slowly.tistory.com/42

알고리즘 : 자료구조(4) 리스트 (List)

#include<iostream>
#include <string>
#include<list>
using namespace std;
int main() {
	string sentence;
	int m;
	cin >> sentence >> m;
	list<char> li(sentence.begin(), sentence.end());
	// list <char>::iterator cusor = li.end();
	auto cusor = li.end();
	while (m--) {
		char command;
		cin >> command;
		switch (command) {
		case 'L': {
			if (cusor != li.begin())
				cusor--;
			break;
		}
		case 'D': {
			if (cusor != li.end())
				cusor++;
			break;
		}
		case 'B': {
			if (cusor != li.begin()) {
				cusor--;
				cusor = li.erase(cusor);
			}
			break;
		}
		case 'P': {
			char x;
			cin >> x;
			li.insert(cusor, x);
			break;
		}
		}
	}
	for (auto i = li.begin(); i != li.end(); i++)
	{
		cout << *i;
	}
}

리스트를 이용하면 조금 더 직관적이게 된다.

 

 

10845. (큐) 정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

#include<iostream>
#include<queue>
using namespace std;
int main() {
	string cmd;
	int n;
	cin >> n;
	queue <int> q;
	while (n--) {
		cin >> cmd;
		if (cmd == "push") {
			int val;
			cin >> val;
			q.push(val);
		}
		else if (cmd == "pop") {
			if (q.empty())
				cout << -1 << "\n";
			else {
				cout << q.front() << "\n";
				q.pop();
			}
		}
		else if (cmd == "size") {
			cout << q.size() << "\n";
		}
		else if (cmd == "empty") {
			cout << q.empty() << "\n";
		}
		else if (cmd == "front") {
			if (q.empty())
				cout << -1 << "\n";
			else
				cout << q.front() << "\n";
		}
		else {
			if (q.empty())
				cout << -1 << "\n";
			else
				cout << q.back() << "\n";
		}
	}
	return 0;
}

c++ stl queue를 사용하면 되는 문제이다.

https://shine-slowly.tistory.com/40

알고리즘 : 자료구조(2) 큐 (Queue) (C++로 구현)

큐를 잘 모른다면 위 글을 읽는 것을 추천한다.

 

 

 

1158. (요세푸스 문제) 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다.

#include<iostream>
#include<queue>
using namespace std;
int main() {
	int k, n;
	cin >> n >> k;
	queue <int> q;
	for (int i = 1; i <= n; i++)
	{
		q.push(i);
	}
	cout << "<";
	while (q.size() != 1) {
		for (int i = 1; i < k; i++)
		{
			int temp = q.front();
			q.pop();
			q.push(temp);
		}
		cout << q.front() << ", ";
		q.pop();
	}
	cout << q.front() << ">";
	q.pop();
	return 0;
}

queue를 이용해 문제를 풀었다. 이 문제도 queue를 안다면 간단하게 풀 수 있는 문제이다. 

 

 

 

10866. (덱) 정수를 저장하는 덱(Deque)를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

#include<iostream>
#include<deque>
using namespace std;
int main() {
	deque <int> dq;
	int n;
	cin >> n;
	string cmd;
	while (n--) {
		cin >> cmd;
		if (cmd == "push_front") {
			int val;
			cin >> val;
			dq.push_front(val);
		}
		else if (cmd == "push_back") {
			int val;
			cin >> val;
			dq.push_back(val);
		}
		else if (cmd == "pop_front") {
			if (dq.empty())
				cout << -1 << "\n";
			else {
				cout << dq.front() << "\n";
				dq.pop_front();
			}
		}
		else if (cmd == "pop_back") {
			if (dq.empty())
				cout << -1 << "\n";
			else {
				cout << dq.back() << "\n";
				dq.pop_back();
			}
		}
		else if (cmd == "size") {
			cout << dq.size() << "\n";
		}
		else if (cmd == "empty") {
			cout << dq.empty() << "\n";
		}
		else if (cmd == "front") {
			if (dq.empty())
				cout << -1 << "\n";
			else 
				cout << dq.front() << "\n";
		}
		else {
			if (dq.empty())
				cout << -1 << "\n";
			else
				cout << dq.back() << "\n";
		}
	}
}

c++ stl deque을 이용하여 풀 수 있다.

https://shine-slowly.tistory.com/41

알고리즘 : 자료구조(3) 덱 (Deque) (C++로 구현)

덱을 모른다면 위 글을 읽고 오는 것을 추천한다.

 

 

 

17413. (단어 뒤집기 2) 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 태그는 단어가 아니며, 태그와 단어 사이에는 공백이 없다.

#include<iostream>
#include<string>
#include <stack>
using namespace std;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	string sentence;
	getline(cin, sentence);
	stack <char> s;
	for (int i = 0; i < sentence.length(); i++)
	{
		if (sentence[i] == ' ') {
			while (!s.empty()) {
				cout << s.top();
				s.pop();
			}
			cout << ' ';
			continue;
		}
		else if (sentence[i] == '<') {
			while (!s.empty()) {
				cout << s.top();
				s.pop();
			}
			while (sentence[i] != '>') {
				cout << sentence[i];
				i++;
			}
			cout << '>';
			continue;
		}
		s.push(sentence[i]);
	}
	while (!s.empty()) {
		cout << s.top();
		s.pop();
	}
	return 0;
}

stack을 이용하여 구현할 수 있다. getline함수는 string을 include해야지 사용할 수 있다.

 

 

 

10799. (쇠막대기) 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저의 배치는 다음 조건을 만족한다.

#include<iostream>
#include<string>
#include <stack>
using namespace std;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	stack <char> stick;
	string laser;
	cin >> laser;
	int num = 0;
	for (int i = 0; i < laser.length(); i++)
	{
		if (laser[i] == '(') {
			stick.push(laser[i]);
		}
		else if (laser[i] == ')' && laser[i - 1] == '(') {
			stick.pop();
			num += stick.size();
		}
		else {
			stick.pop();
			num++;
		}
	}
	cout << num;
	return 0;
}

괄호 문제를 이해했다면 쉽게 풀 수 있는 문제였다. stack에 쌓인 막대의 개수만큼 레이저가 잘랐을 때 발생하게 된다. 그리고 막대의 끝을 만나면 한덩이가 무조건 생기니까 그걸 더해주면 된다.

 

 

다음 자료구조 (2)에서는 오큰수랑 오등큰수를 풀어볼 예정이다. 좀 어려운 것 같아서 따로 포스팅하기로 결정!