[자료구조] 백준 Stack

자료구조: 스택 Stack

 친구들과 스터디를 하면서 첫번째 주제로 잡은 자료구조. 자료구조란 무엇이가. 우리들의 친구 위키는 이렇게 말한다.

자료구조(資料構造, 영어: data structure)는 컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미한다.[1][2][3] 더 정확히 말해, 자료 구조는 데이터 값의 모임, 또 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령를 의미한다.[4] 신중히 선택한 자료구조는 보다 효율적인 알고리즘을 사용할 수 있게 한다.

 여기서 효율적인 접근 및 수정을 가능케하는 자료의 관리, 저장을 위해 우리는 stack, queue, heap 등과 같은 구조를 사용한다. 여기서 스택에 대해 가장 먼저 살펴볼 예정이다! 역시나 백준을 이용하여 공부할 것인데, 문제 > 알고리즘 분류 > 스택에 있는 12문제를 풀어볼 계획이다. 출제수가 가장 많은 수 부터.

 역시나 이번에도 정말 필요한 부분만 노트할 예정.

(코드들은 꼭 풀어보고 참고하세요. c++ )

 

---

 

10828번: 스택

10828번:스택 문제

stack은 모두 어느정도 알거라 생각한다. 후입선출(Last-In-First-Out)이 기본 개념이고 이에 관한 함수는다음과 같다.

push(a) a 값을 스택에 넣는다.
pop() 스택에서 가장 위에 있는 값을 스택에서 제거한다.
size() 스택에 몇 개의 원소가 들어있는지 알려준다.
empty() 스택이 비어있으면 true, 아니면 false를 반환한다.
top() 스택 가장 위에 있는 값을 출력한다.

top()에 대해 조금 더 이야기하자면, stack에 아무 원소가 없을 경우 이 함수를 쓰면 아무 에러 없이 그냥 종료된다. 내가 많이 저지른 실수 중 하나이다.. 그냥 종료된다면 의심해보시길...(´・＿・`)

 아무튼 c++에서는 stack 라이브러리만 include(#include <stack>)해주고 stack<int> s 와 같이 선언해주면 스택 s를 사용가능하다. 중간에 꺽쇠가로 안에는 변수 타입만 넣어주면 된다. 

코드

#include <iostream>
#include <string.h>
#include <stack>
#include <stdlib.h>

using namespace std;

int main(){

	int num;
	int count = 0;

	cin >> num;

	char line[20];
	cin.getline(line, 20);

	stack<int> s;

	while(count < num){
		cin.getline(line, 20);

		if(line[0] == 'p'){
			if(line[1] == 'u'){ // push
				char* a = strtok(line, " ");
				a = strtok(NULL, " ");
				int x = atoi(a);

				s.push(x);
			}
			else{ // pop
				if(s.size() == 0) cout<<"-1"<<endl;
				else{
					cout << s.top() <<endl;
					s.pop();
				} 

			}
		}
		else if(line[0] == 't'){ //top
			if(s.size() == 0) cout << "-1" <<endl;
			else cout << s.top()<< endl;
		}
		else if(line[0] == 's'){ //size
			cout<< s.size() <<endl;
		}
		else if(line[0] == 'e'){ //empty
			if(s.empty()) cout << "1" <<endl;
			else cout<< "0" <<endl;
		}

		count++;
	}

	return 0;
}

 

---

 

2504번: 괄호의 값

2504번:괄호의 값 문제

 이제 어느정도 스택에 대해 정의가 잡혔으면, 활용 문제를 풀어보자. 이 문제는 내가 생각을 좀 많이 했던 문제다. stack과 재귀 함수를 사용하여 문제를 풀었다. 문제를 풀다가 너무 길을 못 잡겠어서, 게시판을 활용한 문제이다. （´＿｀）

 재귀함수(Recursive Function)이란,  말그대로 자기자신의 함수를 다시 부르는 것이다. 개인적으로 많이 사용하는 코딩 법이며, 반복적인 일을 쉬게 하기 위해서 코딩하는 것처럼 뭔가 반복된다 싶으면 사용하는 걸 고려하는 것이 좋다. 여기서 (()[]) 와 같은 예시가 있을 때 이렇게 볼 수 있다. 

(    (     )     [     ]    )

Function(   Function()    Function()  )

함수 하나 안에서 두개의 함수를 부르는 것! 이 문제를 풀면서 내가 다시 생각해본 포인트만 정리해보겠다.

1. count는 전역변수로 설정할 것. 왜냐하면 내가 원하는 검색은 다시 뒤로 돌아가는 것이 아니고 앞으로 쭉 가길 원하거덩. 
2. for(; count < len; count++) 이건 그냥 내가 많이 안써본 코드인데 맨 앞 조건을 이미 정의가 되어 있다면 생략할 수 있다는 것.
3. exit(0) 보통 main 함수에서 이 코드를 종료하고 싶으면 return 0을 한다. 근데 나는 main 함수 안에 있는건 아닌데, 뭔가 잘못되서 그냥 이 실행을 멈추고 싶다? 그러면 exit(0)을 사용해서 종료할 것.

 이정도가 이번 문제에서 다시 기억할 부분들 같다. 이런 조그만한 것들이 모여서 나비효과를 일으킬 것이라 생각한다. 저번 포스트 이후 getline()을 자유자재로 쓸 수 있는 것 처럼! (｀▽´) 

코드

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

using namespace std;
int count = -1;

int Operation(stack<char> &s, string line, int len){
	int result = 0;

	count++;

	for(; count < len ; count++){
		s.push(line[count]);

		if(s.top() == '('){
			result += 2*Operation(s, line, len);
		}
		else if(s.top() == ')'){
			s.pop();
			if(s.empty() || s.top() != '('){
				cout << 0 <<endl;
				exit(0);
			}

			else{
				s.pop();
				if(result == 0) return 1;
				else return result;
			}
		}
		else if(s.top() == '['){
			result += 3*Operation(s, line, len);
		}
		else if(s.top() == ']'){
			s.pop();
			if(s.empty() || s.top() != '['){
				cout << 0 <<endl;
				exit(0);
			}

			else{
				s.pop();
				if(result == 0) return 1;
				else return result;
			}
		}
	}

	return result;
}

int main(){

	string a;
	stack<char> s;
	int result;
	int count = -1;
	
	getline(cin, a);

	int len = a.size();

	if (a[len - 1] == '(' || a[len - 1] == '['){
		cout << 0 << endl;
		return 0 ;
	}

	result = Operation(s, a, len); 

	if(!s.empty()){
		cout << 0<< endl;
		return 0;
	}
	else cout << result;

	return 0;
}