[백준/BOJ] 28278번 : 스택 2 ( Stack 자료 구조 사용하기 ) - C++ 문제 풀이

문제 설명

 

문제 링크: http://www.acmicpc.net/problem/28278

28278번: 스택 2

 

풀이

문제에서는 스택을 구현해서 문제를 풀라고 되어있지만, std::stack 클래스를 사용해서 문제를 풀었다.

숫자를 읽어서 그 숫자에 따라 std::stack 클래스의 각 기능을 사용하면 간단히 처리된다.

한번 스택을 구현해 보라는 문제인 거 같다.

 

나머지 글도 대부분 stack 자료 구조와 std::stack 클래스 사용법에 대하여 적을 생각이다.

 

스택(Stack)은 컨테이너의 한 종류로서 스택에 입력된 데이터가 먼저 출력될 수 있는 자료 구조입니다.

맨 나중에 입력된 데이터가 먼저 출력되어야 하는 LIFO (Last Input First Out) 구조로서, 자료 접근에 제한된 기능을 가집니다.

 

스택(Stack)의 구조

 

 

이런 구조는 예전 상태로 돌아가는 기능을 구현할 때 많이 고려됩니다.

예를 들어, 워드프로세서의 Undo 기능, 웹 브라우저의 돌아가기 기능 등이 있습니다.

 

std::stack 클래스를 사용하려면 다음 헤더를 포함해야 합니다.

#include <stack>

 

std::stack 클래스의 멤버 함수는 다음과 같습니다.

함        수		설              명
empty		스택이 비었는지 검사합니다. 비었으면 true를 리턴합니다.
pop		스택의 가장 상위 멤버를 제거합니다.
push		스택에 멤버를 가장 상위에 추가합니다.
size		멤버의 개수를 리턴합니다.
top		스택의 가장 상위에 있는 멤버의 참조를 리턴합니다.

 

top 멤버 함수를 호출 시 가장 상위에 있는 멤버의 참조(reference)를 리턴하므로, 스택이 비어있으면 오류가 발생합니다.

이를 방지하기 위해 empty 함수 같은 테스트를 거쳐야 합니다.

stack<int> st;

if (!st.empty()){
	int a = st.top();
}

 

마지막으로,  그냥 cin 객체를 사용해서 입력받으면 "시간제한"에 걸립니다.

그래서 main함수 시작 시, 두 줄을 추가했습니다.

ios::sync_with_stdio(false);
cin.tie(NULL);

 

첫 번째 ios::sync_with_stdio(false)를 호출하면 C runtime library와 입출력 동기화가 제거됩니다.

C 입출력 함수인 scanf, printf 등과 같이 사용했을 때, 결과를 보장할 수 없다는 뜻입니다.

그렇지만 그 대신 cin 개체를 사용할 때 속도가 향상됩니다.

(궁금하신 분들은 이 코드를 제거하고 테스트해 보시길 바랍니다.)

 

두 번째 cin의 tie(NULL) 함수는 cout 개체와의 동기화를 제거합니다.

기본적으로 동기화되어 있기 때문에 다음 코드는 "숫자를 입력하세요." 문장이 먼저 보인 후, 숫자 입력을 대기합니다.

cout << "숫자를 입력하세요." << "\n";

int num;
cin >> num;

그렇지만, 동기화를 제거하면 "숫자를 입력하세요." 글자를 보기 전에 숫자 입력을 대기하는 상황이 생길 수도 있습니다.

그 대가로 이 코드 역시 속도가 향상됩니다. 문제에서는 동기화가 필요 없으므로 기능을 제거했습니다.

 

 

소스 코드

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

int main() {

    ios::sync_with_stdio(false);    // C runtime library와 동기화 제거
    cin.tie(NULL);       	// cout과 동기화 제거
    
    int N;
    cin >> N;

    int cmd, num;
    stack<int> st;

    for(int i=0; i < N; i++){

        cin >> cmd;
        if ( cmd == 1){
            cin >> num;
            st.push(num);
        }
        else if ( cmd == 2 ){
            
            if ( st.size() == 0 ) num = -1;	// top 호출 시, 스택이 비었는지 확인
            else{
                num = st.top();
                st.pop();
            }  
            cout << num << "\n";
        }
        else if ( cmd == 3){
            num = st.size();
            cout << num << "\n";
        }
        else if ( cmd == 4){
            num = st.size();
            num = (num == 0) ? 1 : 0;
            cout << num << "\n";
        }
        else if ( cmd == 5){
            if ( st.size() == 0 ) num = -1;
            else{
                num = st.top();
            }  
            cout << num << "\n";
        }
    }

    return 0;
}