[알고리즘] 크레인 인형뽑기 게임

포인트

• 문제에서는 친절히 스택을 써주라고 그림에서 보여준다. (하지만 나는 바로 알지 못했다.)
• MOVES 는 열의 숫자로 본인은 0을 쓰는 것을 좋아하기 때문에 잘 사용하기 위해 수정을 하였다.

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

c++/cpp

#include <bits/stdc++.h>

using namespace std;

int solution(vector<vector<int>> board, vector<int> moves)
{
    int answer = 0;
    for (int i = 0; i < moves.size(); i++)
    {
        moves[i] -= 1;
    }
    stack<int> stack;

    for (auto command : moves)
    {
        for (int i = 0; i < board.size(); i++)
        {
            if (board[i][command] != 0)
            {
                stack.push(board[i][command]);
                board[i][command] = 0;
                break;
            }
        }

        if (stack.size() >= 2)
        {
            auto a = stack.top();
            stack.pop();
            auto b = stack.top();
            stack.pop();

            if (a == b)
            {
                answer += 2;
            }
            else
            {
                stack.push(a);
                stack.push(b);
            }
        }
    }

    return answer;
}

python

def solution(board: list, moves: list) -> int:
    moves = list(map(lambda x: x - 1, moves))
    # 순서를 맞추기 위해 전부 하나씩 빼준다 
    stack = []
    answer = 0
    
    for command in moves:
        # 움직임을 보면서
        for row in range(len(board)):
            if board[row][command] != 0:
                # 0이 아닌 것을 만나면
                stack.append(board[row][command])
                # 일단 스택에 넣고
                board[row][command] = 0
                # 0으로 바꾼다
                break

        if len(stack) >= 2 and stack[-1] == stack[-2]:
            # 2이상 이고 같다면 2개를 빼고 넣는다.
            stack.pop(-1)
            stack.pop(-1)
            answer += 2

    return answer


print(solution([[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]],
               [1, 5, 3, 5, 1, 2, 1, 4]))
# 4