크레인 인형뽑기 게임 (feat. 프로그래머스, 64061번)

크레인 인형뽑기 게임
https://school.programmers.co.kr/learn/courses/30/lessons/64061

프로그래머스

반응형

// woohyeon.kim
#include <string>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

int solution(vector<vector<int>> board, vector<int> moves) {
    int answer = 0;
    auto cp_board = board;
    auto N = board.size();
    for(auto ix = 0; ix < N; ++ix)
    {
        for(auto iy = 0; iy < N; ++iy)
        {
            board[ix][iy] = cp_board[iy][ix];
        }
        reverse(board[ix].begin(), board[ix].end());
    }
    stack<int> tmpl;
    for(const auto& move : moves)
    {
        while(!board[move - 1].empty())
        {
            auto v = board[move - 1].back();
            board[move - 1].pop_back();
            if(v == 0)                  continue;
            if(tmpl.empty())            tmpl.push(v);
            else
            {
                if(tmpl.top() == v)
                {
                    tmpl.pop();
                    answer += 2;
                }
                else                    tmpl.push(v);
            }
            break;
        }
    }
    return answer;
}
// *&)*@*

2차 벡터의 행렬 순서를 바꿔주고 FILO의 자료구조인 stack을 사용하면 간단하게 해결할 수 있어요!

문제는 "지금 stack에 총 몇개가 남았는가" 가 아니라 "터진 풍선의 개수는 총 몇개인가" 입니다.

즉, 답은 무조건 2의 배수여야 한다는 것이죠!