백준 10828번 - 스택 (Stack)

 

 

 

* 문제 링크

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

10828번: 스택

 

 

 

문제 내용 요약

 

문제에서 요구하는 명령어를 구현하는 것으로 스택이란 것을 구현해보자.

 

 

 

 

접근법 (스택이란 무엇인가?)

 

 

매우매우 중요한 자료구조 중 하나인 "스택"을 구현하는 문제다.

 

이 밑은 "스택"에 대한 설명으로 시작하고,

 

Linked List는 귀찮기 때문에 간단하게 배열을 이용해서 스택을 구현하는 느낌으로 설명을 할 것이지만,

 

그 밑에 코드는 C++ 의 "stack" 라이브러리를 이용해서 날로 먹는 코드이기 때문에 주의가 필요하다.

 

참고로 상세 구현법이 하나만 있지는 않기 때문에, 사람마다 다를 수 있다.

 

 

여느 자료구조/알고리즘이 다 그렇지만 처음에는 밑바닥에서 구현해보고,

 

이후에 누군가가 잘 만들어놓은 라이브러리를 이용하는 것이 나에게도, 컴퓨터에게도 이롭다. 

 

 

 

간단한 예시로 시작해보자.

 

우리가 어떤 적당한 바닥에 책을 쌓아놓았다.

 

다른 책을 건드리지 않고 하나만 빼기에 적당한 곳을 어디인가? 바로 가장 위에 있는 책을 빼는 것이다.

 

쌓을 때는 어떤가? 똑같이 가장 위에다가 책을 쌓을 것이다.

 

어 저는 중간/밑에서 빼는데요? 축하합니다. 당신은 굳이 그 곳에 있는 책을 빼셨고, 책더미는 넘어졌습니다.

 

 

 

어쨌든 이런 식으로 가장 마지막에 넣은 것을 가장 먼저 빼는 형태(LIFO, Last In First Out)의 자료구조를

 

"스택(Stack)"이라고 한다.

 

 

 

배열을 썼지만, 인덱스는 쓰지 않을 것이다. 스택에서는 오직 "Top" 에 있는 값만 엑세스 가능하기 때문이다. 

 

"Top"의 초기 위치를 '-1'로 시작하는 것으로 했다.

 

 

 

처음에는 위의 그림과 같은 빈 스택이 있다고 하자. 그리고 값을 넣어보자.

 

push 5	// 5를 스택에 넣는다
push 8	// 8를 스택에 넣는다
push 3	// 3를 스택에 넣는다
top	// top이 가리키는 곳의 값을 출력한다 / 스택의 가장 위의 값을 출력한다.

 

push 5

push 8

push 3, top

 

"push" 명령의 경우, size 는 1 증가, Top의 위치 또한 1씩 증가시켜주고, 값을 넣어주면 된다.

 

여기서 "top" 명령으로는 스택의 가장 위의 값을 출력하면 되고, 3이 출력될 것이다.

 

대충 아래와 같이 구성하면 된다. (주의!! 정확한 코드가 아닌 의미 전달용 유사 코드다.)

 

/* 주의!! 의미 전달용 코드. 돌아가지 않음 */

push(int n) {
    Top++;
    size++;
    stack[Top]=n;
}

top() {
    if(size==0) return -1;
    return stack[Top];
}

 

 

 

 

이번엔 값을 빼내보자.

 

 

pop	// 스택의 가장 위 값을 출력하고 제거한다.
pop	// 스택의 가장 위 값을 출력하고 제거한다.
top	// 스택의 가장 위 값을 출력한다.

/* C++ 의 <stack> 라이브러리에서 'pop'은 가장 위 값을 스택에서 제거만 하고 반환하지 않는다. */

 

pop

pop, top

 

"pop"은 Top의 위치에 있는 값을 저장하고, 제거한 후에(제거하지 않아도 되긴 하다)

 

Top과 size의 값을 1씩 감소시키면 된다.

 

주석에도 썼지만 c++ stack의 경우 pop은 값을 제거만 한다.

 

이 문제의 경우, pop은 값을 출력하고 제거하기 때문에, top 명령까지 포함하면 다음과 같은 결과가 나올 것이다.

 

3
8
5

 

구성은 아래와 같이 될 것이다. size가 0, 즉 들어있는 값이 없으면 -1을 뱉는다.

 

내 기억으로 c++ 라이브러리에서는 값이 없으면 에러를 띄웠던 것 같다.

 

/* 주의!! 의미 전달용 코드. 돌아가지 않음 */

pop() {
    if(size==0) return -1;
    
    int n = stack[Top]
    size--;
    Top--;
    return n;
}

 

 

 

 

이번엔 size와 empty를 보자.

 

size
empty
pop
size
empty
pop

size, empty

pop, size, empty, pop

 

출력은 아래처럼 될 것이다.

 

1	//size
0	//empty
5	//pop
0	//size
1	//empty
-1	//pop

 

size는 미리 만들어둔 size 변수값을 그대로 반환하면 되고, empty는 size 값이 0인지 확인해주면 될 것이다.

 

/* 주의!! 의미 전달용 코드. 돌아가지 않음 */

size() { return size; }
empty() { return size==0; }

 

 

 

그러면 얼추 이 문제를 풀기 위한 5가지의 명령에 대해서 코드를 짤 수 있을 것이다.

 

c++ 할 줄 안다면 <stack> 써서 이 문제를 날로 먹자.

 

물론 약간의 수정은 필요할 것이다.

 

 

 

 

 

내 코드

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

int main() {
	int n;
	string s;
	stack<int> S;
	cin>>n;
	for(int i=0;i<n;i++) {
		cin>>s;
		if(s.compare("push")==0) {
			int t;
			cin>>t;
			S.push(t);
		} else if(s.compare("pop")==0) {
			if(S.empty()) printf("-1\n");
			else {
				cout<<S.top()<<endl;
				S.pop();
			}
		} else if(s.compare("size")==0) {
			cout<<S.size()<<endl;
		} else if(s.compare("empty")==0) {
			cout<<S.empty()<<endl;
		} else {
			if(S.empty()) printf("-1\n");
			else cout<<S.top()<<endl;
		}
	}
}

 

 

 

 

 

여담

 

어떤 플래4 난이도의 문제 풀이 글을 쓰려다가

 

어떤 두 알고리즘에 대한 글이 필요한 것을 깨달았는데,

 

그 중 하나의 알고리즘을 쓰기 위해 큐에 대한 설명이 필요한데

 

그것과 비슷한 알고리즘은 또 스택을 쓰다보니

 

흐르고 흘러 이거부터 쓰기로 결정했다.

 

글 하나 쓰기 위해 4개 이상의 사전 작업을 하다니

 

귀찮네......