2019 카카오 개발자 겨울 인턴십 - 크레인 인형뽑기 게임

문제 링크 : programmers.co.kr/learn/courses/30/lessons/64061

코딩테스트 연습 - 크레인 인형뽑기 게임

 

문제 풀이

$N * N$으로 이루어진 2차원 정수 벡터 board와 크레인을 어느 열(column)에서 작동시켰는지를 의미하는 1차원 정수 벡터 moves가 주어진다.

board에는 인형이 들어있는데 인형은 $[1, 100]$ 정수로 표현되고 0인 경우에는 인형이 없는 것이다.

크레인은 인형을 집어서 바구니에 스택 형태로 쌓게 되는데, 바구니에 인형을 넣을 때 동일한 인형이 2개가 되면 해당 인형은 터져서 사라진다.
(또한, 문제에서 바구니는 모든 인형이 들어갈 수 있을 만큼 크다고 가정했으므로 바구니 크기는 고려하지 않아도 된다.)

이처럼 크레인이 모든 이동을 마쳤을 때 바구니에서 터지는 인형이 몇 개인지 반환하면 되는 구현 문제이다.

 

 

소스 코드

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

int solution(vector<vector<int>> board, vector<int> moves) {
    int answer = 0;
    stack<int> basket;
    const int N = (int)board.size(); // N*N
    
    for (int c : moves) {
        --c; // column idx : [0, N)
        for (int r = 0; r < N; ++r) {
            if (board[r][c] == 0) continue;
            if (!basket.empty()) {
                int topElem = basket.top();
                if (topElem == board[r][c]) {
                    basket.pop();
                    answer += 2;
                }
                else {
                    basket.push(board[r][c]);
                }
            }
            else {
                basket.push(board[r][c]);
            }
            board[r][c] = 0;
            break;
        }
    }
    
    return answer;
}