[프로그래머스] 크레인 인형뽑기 게임

[프로그래머스] 크레인 인형뽑기 게임

• https://programmers.co.kr/learn/courses/30/lessons/64061

• 2차원 배열로 board가 주어졌을 때 크레인은 각 열에 대해 뽑기를 한다.
  -> board의 정보를 각 열 별로 나눠서 저장하는 것이 편리하다.

• 크레인이 뽑기를 할 때와 바구니에 담긴 인형을 확인할 때, 맨 위에 있는 요소에 대해서만 연산을 한다.
  -> stack 자료구조를 이용하는 것이 편리하다.

#include <string>
#include <vector>
#include <stack>

using namespace std;

int solution(vector<vector<int>> board, vector<int> moves) {
	int answer = 0;

	vector<stack<int>> boardSt(30);
	stack<int> st;
	
    //board의 맨 아래에서 위로 순회하며 board의 열의 정보를 각 열에 대응되는 stack에 저장
	for (int i = board.size() - 1; i >= 0; --i) {
		for (int j = 0; j < board.size(); ++j) {
			if (board[i][j] != 0) boardSt[j].push(board[i][j]);
		}
	}

	for (int m = 0; m < moves.size(); ++m) {
		int pos = moves[m] - 1;
		if (boardSt[pos].empty()) continue;

		int num = boardSt[pos].top();
		boardSt[pos].pop();

		if (!st.empty() && st.top() == num) {
			st.pop();
			answer += 2;
		}
		else st.push(num);
	}

	return answer;
}