프로그래머스 크레인인형뽑기 게임 c++ // stack, 구현

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

프로그래머스

1. 의사코드

1.1. 

0 0 0 0 0

0 0 1 0 3

0 2 5 0 1

4 2 4 4 2

3 5 1 3 1 일때,

vector<stack<int>>에 4,3 / 2,5,2 / 1,5,4,4,1 ... 이렇게 세로로 담는다.

 

2.2 바구니(s)와 현재탐색중인 stack(v[i-1])의 top을 비교하면서

같으면 s.pop && answer++

다르면 s.push한다.

 

2. 전체코드

#include <bits/stdc++.h>

using namespace std;

vector<stack<int>> v;
stack<int> s;   //뽑은애들

int solution(vector<vector<int>> board, vector<int> moves) {
    int answer = 0;
    int n=board.size()-1;
    
    for(int x=0;x<n+1;++x){
        stack<int> temp;
        for(int y=n;y>=0;--y){
            if(board[y][x]==0) continue;
            temp.push(board[y][x]);
        }
        v.push_back(temp);
    }
    
    // for(auto ss:v){
    //     while(ss.size()){
    //         cout<<ss.top()<<" ";
    //         ss.pop();
    //     }
    //     cout<<"\n";
    // }
    
    
    for(int i : moves){
        if(v[i-1].size()){
            if(s.size() && s.top()==v[i-1].top()){
                s.pop();
                answer++;
            }
            else{
                s.push(v[i-1].top());
            }
            v[i-1].pop();
        }
        
    }
    
    return answer*2;    //인형은 한번터질때 2개씩 터짐
}