크레인 인형뽑기 게임

문제설명1

문제설명 2

 

[제한사항]

• board 배열은 2차원 배열로 크기는 "5 x 5" 이상 "30 x 30" 이하입니다.
• board의 각 칸에는 0 이상 100 이하인 정수가 담겨있습니다.
  • 0은 빈 칸을 나타냅니다.
  • 1 ~ 100의 각 숫자는 각기 다른 인형의 모양을 의미하며 같은 숫자는 같은 모양의 인형을 나타냅니다.
• moves 배열의 크기는 1 이상 1,000 이하입니다.
• moves 배열 각 원소들의 값은 1 이상이며 board 배열의 가로 크기 이하인 자연수입니다.

입출력 예

board                                                                                                                                               moves                             result

[[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

입출력 예에 대한 설명

입출력 예 #1

인형의 처음 상태는 문제에 주어진 예시와 같습니다. 크레인이 [1, 5, 3, 5, 1, 2, 1, 4] 번 위치에서 차례대로 인형을 집어서 바구니에 옮겨 담은 후, 상태는 아래 그림과 같으며 바구니에 담는 과정에서 터트려져 사라진 인형은 4개 입니다.

 

 

 

#include <string>
#include <vector>
#include <stack> 
#include <iostream>

using namespace std;

int solution(vector<vector<int>> board, vector<int> moves) {
    int answer = 0;
    stack<int> st; 
    
    for(int i=0; i<moves.size(); i++) // 뽑을 행 , +1을 하여 계산
    {
        for(int j=0; j<board.size(); j++)
        {
          
            if(board[j][moves[i]-1] != 0)
            {
                if(!st.empty() )//스택에 쌓여져 있을 경우
                {
                    if(st.top() == board[j][moves[i]-1])
                    {
                        st.pop();
                        answer+=2;
                    }
                    else
                    {
                        st.push(board[j][moves[i]-1]);
                    }
                }
                else
                {
                    st.push(board[j][moves[i]-1]);
                }
                board[j][moves[i]-1]=0;
                break;
            }
        }
    }
    return answer;
}

=> 단순구현문제입니다. 

=> moves의 index를 탐색하며 해당 값에 해당하는 board에 0이 아닌 값을 찾는 것을 찾아야합니다. 

=> 끝까지 0이 없을 경우 지속하며, 0이 아닌 값을 찾은 경우 적절히 조작하여 문제가 원하는 값을 구합니다. 

=> STACK에 쌓여있는 TOP()과 현재 STACK에 PUSH할 값과 동일할 경우, POP을 해야하며 ANSWER+=2; 를 해주어야합니다. 

=> 예시에서 BOARD의 사이즈는 5였지만, 더 클 수 있음을 염두에 둬야합니다.