프로그래머스 - 크레인 인형뽑기 게임

프로그래머스 - 크레인 인형뽑기 게임

카카오 문제들은 뭔가 길다.. 그래서 그림을 보고 이해를 먼저 하고, 그 다음 지문을 읽는다.

문제는 간단한 스택 문제이다.
[[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]]
이런 식으로 board값이 주어지고,
[1,5,3,5,1,2,1,4]
이런 식으로 move값이 주어진다.

board의 각 coloumn이 moves의 1,2,3,4,5 에 대응된다. moves의 1이 의미하는 것은 board[x][i]에서 1개를 뽑는 것이고, 여기서 x는 가장 높은 높이라 생각하면 된다...

각 column마다 높이를 관리하는 height를 따로 관리해주면 굳이 board를 전치해서 사용할 필요도 없고, 가장 높이있는 entry를 1번만에 바로 찾아갈 수 있다.

코드는 아래와 같다.

#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();
    int x = board[0].size();
    stack<int> st;
    vector<int> height(h, 0);
    for(int i=0;i<h;i++) 
        for(int j=0;j<x;j++) 
            if(board[i][j] != 0 && height[j] == 0) 
                height[j] = h - i;
     
    int size = moves.size();
    for(int i=0;i<size;i++) {
        int target = moves[i] - 1;
        if(height[target] == 0)
            continue;
        int targetNum = board[h - height[target]][target];
        if(st.empty()) 
            st.push(targetNum);
        else {
            int topNum = st.top();
            if(topNum != targetNum) 
                st.push(targetNum);
            else {
                answer+=2;
                st.pop();
            }
        }
        height[target]--;
    }
    return answer;
}