[programmers] 크레인 인형 뽑기 (in C++)

문제

크레인 인형 뽑기
N * N 배열에서, 크레인의 움직임에 따라 인형 하나가 올라온다.
잡힌 인형은 바구니에 담겨진다.
이때, 바구니의 맨 위에 있는 인형과 잡힌 인형이 같으면 터뜨려서 사라지게 한다.
크레인의 움직임이 멈췄을 때, 사라진 인형의 갯수를 구하여라.

접근

바구니는 stack으로 쌓이게 된다. 이 stack의 top과 잡힌 인형을 비교하여
같다면 stack pop을 한 뒤, 사라진 인형의 총 갯수를 +2한다. 만약 다르다면
stack에 Push한다.

복잡도

• 공간 복잡도 : N*N
• 시간 복잡도 : N
  • 크레인의 움직임이 들어있는 N길이의 배열을 한 번 순회한다.

알게된 점

1. C++ 참조형 변수
   moveAndPopToy에서 파라미터로 받은 board를 참조하지 않고 그냥 받았을 때,
   moveAndPopToy에서 board의 값을 변화시켜도 solution에서 넘겨준 board에는 변화가 없었다.
   이는 변화된 값은 solution에서 인자로 넘겨준 board와 다른 메모리에 있는 값이기 때문이었다.
   C++의 참조형 변수를 사용하여 moveAndPopToy이 인자로 받은 board는 solution에 있는 board를 참조하도록 하여 해결하였다.

2. vector.back() 참조 에러
   basket.back()을 하였을 때 에러가 발생하였다. 이는 처음에 basket에 어떠한 값도 들어있지 않기 때문에, 접근 시 에러가 발생하는 것이었다.
   따라서 basket이 비어있는지 확인한 후, 비어잇지 않으면 back()으로 벡터의 마지막을 참조하고자 하였다.

코드

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

vector<int> basket;
const int EMPTY = 0;
int nLine;
int nPopped;


void pushOrPopToBasket(vector<vector<int>> board, int toy){
  if(!basket.empty() && basket.back() == toy){
    basket.pop_back();
    nPopped += 2;
  }else{
    basket.push_back(toy);
  }
}

void moveAndPopToy(int column, vector<vector<int>> &board){
  for(int r = 0; r < nLine; r++){
    if(board[r][column] == EMPTY){
      continue;
    }
    pushOrPopToBasket(board, board[r][column]);
    board[r][column] = EMPTY;
    break;
  }
}


int solution(vector<vector<int>> board, vector<int> moves){
  nLine = board.size();
  int nMove = moves.size();
  for(int i = 0; i < nMove; i++){
    int targetColumn = moves[i]-1;
    moveAndPopToy(targetColumn, board);
  }

  return nPopped;
}