[프로그래머스] 크레인 인형뽑기 c++

문제 링크 

 

리뷰 

크레인은 칸의 최상위 인형만 뽑을 수 있다. 그래서 board 열 개수만큼 스택을 선언했다. 

board의 가장 아래 열 부터 0번째 열 방향으로 순회하면, 스택에 문제 그림과 비슷하게 인형이 쌓인다. 

 

크레인의 접근 열 순서를 담고있는 배열 moves 를 순회하여 열 번호에 해당하는 stack 을 확인한다. 

stack의 top을 확인하기 전에, stack의 크기가 0 이 아닌지 확인해야 한다. 

 

"맞았습니다" 코드 

#include <string>
#include <vector>
#include <stack>
using namespace std;

int solution(vector<vector<int>> board, vector<int> moves) {
  int answer = 0;
  int h = board.size(), w = board[0].size();

  vector<stack<int>> v(w+1); // 칸 마다 스택 만들어둔다
  stack<int> basket; // 바구니 

  for(int i = h-1; i >= 0; i--){
    for(int j = 0; j < w; j++ ){
      if(board[i][j] != 0) v[j].push(board[i][j]);
    }
  }

  for(int m = 0; m < moves.size(); m++){
    int i = moves[m]; // 크레인이 인형을 꺼낼 칸 번호  
    if(v[i-1].size() == 0) continue; // 칸에 인형이 없으면 지나감 

    int target = v[i-1].top(); // target: 인형 번호 
    v[i-1].pop();

    if(basket.size() > 0 && basket.top() == target) {
      basket.pop(); answer += 2;
    } else basket.push(target);
  }
  return answer;
}