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

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

프로그래머스

 

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

int solution(vector<vector<int>> board, vector<int> moves) {
    int answer = 0;
    stack<int> s;
    vector<int>arr(board.size(), 0);
    for (int i = 0; i < arr.size(); i++)
    {
        for (int j = 0; j < arr.size(); j++)
        {
            if (board[j][i] != 0)
            {
                arr[i] = j;
                break;
            }
        }
    }
    for (int i = 0; i < moves.size(); i++)
    {
        moves[i]--;
        if (arr[moves[i]] == board.size())continue;
        int cur = board[arr[moves[i]]][moves[i]];
        if (cur != 0)
        {
            if (s.empty())
                s.push(cur);
            else
            {
                if (s.top() == cur)
                {
                    s.pop();
                    answer += 2;
                    
                }
                else
                    s.push(cur);
            }
            arr[moves[i]]++;
        }
    }
    return answer;
}

 

인형의 종류가 2차원벡터인 board로 주어지고 크레인이 움직인 위치가 moves로 주어진다. 

뽑은 인형은 바구니에 하나씩 쌓인다 가정하며 같은 종류 2개가 쌓이면 터지며 +2점이 된다.

이 때, 얻은 점수를 리턴하는 문제이다.

 

먼저 arr 벡터에 board에서 각 줄에서 가장 위에있는 인덱스를 저장한다. 

arr 벡터를 통해 한번에 크레인이 뽑을 위치에 접근한다.

 

for (int i = 0; i < moves.size(); i++)
    {
        moves[i]--;
        if (arr[moves[i]] == board.size())continue;
        int cur = board[arr[moves[i]]][moves[i]];
        if (cur != 0)
        {
            if (s.empty())
                s.push(cur);
            else
            {
                if (s.top() == cur)
                {
                    s.pop();
                    answer += 2;

                }
                else
                    s.push(cur);
            }
            arr[moves[i]]++;
        }
    }

moves위치에서 하나씩 뽑아서 바구니에 쌓는다. 

moves[i]는 크레인이 움직인 보드의 열에 해당한다.

arr[moves[i]] 는 보드의 열에서 가장 위에있는 인형의 위치에 해당한다.

따라서 board에서 크레인이 움직인 위치의 열에서 가장 위에있는 인형의 위치가 cur에 저장된다.

 

그리고 stack을 통해서 계속 쌓거나 이전값과 cur가 동일하면 같은 인형이므로 +2점 계산한다.