문제 링크

풀이 )

  현재 입력된 값과 비교하면서 1부터 stack에 집어넣고, 출력을 위한 vector에 '+'를 넣는다.

  현재 입력된 값과 stack의 top이 일치하면 pop하고, 출력을 위한 vector에 '-'를 넣는다.

  이 후 stack이 비어있는 경우, 즉 수열을 만들 수 있는 경우 vector의 원소를 모두 출력하고,

  비어있지 않은 경우 "NO"를 출력한다.

#include <iostream>
#include <vector>

using namespace std;

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<char> vc;
    vector<int> vi;
    int vi_input = 1;
    while(n--){
        int seq;
        cin >> seq;
        while(vi_input<=seq){
            vi.push_back(vi_input++);
            vc.push_back('+');
        }
        if(vi.back() == seq){
            vi.pop_back();
            vc.push_back('-');
        }
    }
    if(vi.empty()){
        for(vector<char>::iterator it = vc.begin(); it != vc.end(); ++it)
            cout << *it << '\n';
    }
    else
        cout << "NO" << endl;
    return 0;
}

주의 )

  결과 출력 시 줄바꿈에 std::endl 사용 시 시간초과가 난다.

문제 링크

풀이 )

  "0"이 지울 수 있음이 보장되어있으므로, 0이 아니면 push, 0이면 pop한 뒤

  마지막에 stack에 있는 모든 원소들을 더해준다.

#include <iostream>
#include <stack>

using namespace std;

int main(void){
    int n;
    stack<int> st;
    cin >> n;
    while(n--){
        int input;
        cin >> input;
        if(input)
            st.push(input);
        else
            st.pop();
    }
    int sum = 0;
    while(!st.empty()){
        sum += st.top();
        st.pop();
    }
    cout << sum << endl;
    return 0;
}

문제 링크

풀이 )

  줄 개수만큼의 stack을 만든 후 새로 줄을 따라서 stack에 넣어줬다.

  st[0] = 12, 13, 21, 48, 52

  st[1] = 7, 8, 10, 14, 20

  st[2] = 9, 11, 26, 28, 32

  st[3] = 15, 19, 31, 35, 41

  st[4] = 5, 6, 16, 25, 49

  이후 각 stack의 top을 비교하여 총 n-1번에 거쳐 가장 큰 수를 제거한다.

  st[0] = 12, 13, 21

  st[1] = 7, 8, 10, 14, 20

  st[2] = 9, 11, 26, 28, 32

  st[3] = 15, 19, 31, 35

  st[4] = 5, 6, 16, 25

  마지막으로 각 stack의 top 중 가장 큰 값을 출력한다.

#include <iostream>
#include <stack>
#include <algorithm>

using namespace std;

int main(void){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	cin >> n;
	stack<int> st[n];
	for(int i = 0; i < n; ++i){
		for(int j = 0; j < n; ++j){
			int tmp;
			cin >> tmp;
			st[j].push(tmp);
		}
	}
	for(int i = 0; i < n-1; ++i){
		int max_idx = 0;
		for(int j = 1; j < n; ++j){
			if(st[max_idx].top() < st[j].top()){
				max_idx = j;
			}
		}
		st[max_idx].pop();
	}

	int ans = st[0].top();
	for(int i = 1; i < n; ++i)
		ans = max(ans, st[i].top());
	cout << ans << endl;
	return 0;
}

주의 )

- cin을 사용하는 경우 std::ios::sync_with_stdio(false); std::cin.tie(nullptr);을 하지 않으면 시간초과가 난다.

- 단순히 모든 숫자를 정렬해서 n번째 수를 출력하려고 한다면 정렬하는데 최대 입력인 1500*1500에 대해서 nlogn의 시간이 소요되기 때문에 시간초과가 난다.

문제 링크

풀이 )

• 바구니(basket)가 비어있는 경우 선택된 인형(picked)을 그대로 넣고
• 바구니가 비어있지 않은 경우 basket에서 가장 위에 있는 인형(basket.back())과 인형을 비교해서
  • 같은 경우 선택된 인형과 가장 위의 인형을 제거 하기 위해서 basket.pop_back()을 하고 답에 2를 더하고
  • 다른 경우 선택된 인형을 바구니에 넣는다. basket.push_back(picked)

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> board, vector<int> moves) {
    int answer = 0;
    int len_moves = moves.size();
    int len_board = board.size();
    int picked;
    vector<int> basket;

    for(int i = 0; i < len_moves; ++i){
        int crain = moves[i]-1;
        for(int j = 0; j < len_board; ++j){
            if(picked = board[j][crain]){
                board[j][crain] = 0;
                if(basket.empty()){
                    basket.push_back(picked);
                    break;
                }
                if(basket.back() == picked){
                    basket.pop_back();
                    answer += 2;
                }
                else
                    basket.push_back(picked);
                break;
            }
        }
    }
    return answer;
}

주의점 )

• 인형을 뽑은 이후 board에서의 값을 0으로 변경
• 인형을 고른 후 작업을 마친 다음 break

LIFO 문맥에서 동작하기 위해 설계된 컨테이너 어댑터

stack의 top으로 알려진 container의 back에서 push와 pop

멤버 함수

생성

#include <iostream>
#include <stack>
#include <vector>
#include <deque>

using namespace std;

int main(){
    deque<int> deq(3, 100);
    vector<int> vc(2, 200);

    stack<int> first;    // 빈 스택
    stack<int> second(deq);     // deque를 복사하여 초기화
    stack<int, vector<int>> third;
    stack<int, vector<int>> fourth(vc);
}

용량

• empty()
• size()

제어

• top()
• push()
• pop()
• emplace() * C++11
• swap() * C++11

#include <iostream>
#include <stack>

using namespace std;

int main(){
    stack<int> st;
    int sum = 0;

    for(int i = 1; i <= 10; ++i)
        st.push(i);
    cout << st.size() << endl;
    // 10

    while(!st.empty()){
        sum+= st.top();
        st.pop();
    }

    cout << sum << endl;
    // 55
}