[프로그래머스] 크레인 인형뽑기 c++

문제 설명

n행마다 인형이 쌓여져 있다.

인형은 moves 원소로 표현된다.

주어진 moves와 board에 따라 쌓여져 있는 맨 위의 원소를 꺼내 새로운 저장소에 담는다.

이 때, 같은 인형 번호가 2개가 만나면 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

풀이

인형을 순차적으로 꺼내기 위해서 index의 시작이 0부터 인지 n 부터인지 나와있지 않아 헷갈렸다.

그림과 board 벡터의 원소들을 매칭해보았다.

이렇게 해보니 어떤 룰인지 이해가 갔다.

baord[0]이 맨 아래 행으로 생각했는데 아니였다. board[0]이 맨 위에 위치해서 제일 먼저 인형이 꺼내지는 곳이다.

또한, 표를 그려서 board와 moves에 따라 인형뽑기 룰을 이해했다.

마지막 결과 표와 아래 결과 그림이 같다는 것을 확인 할 수 있다.

위에 표를 코드화하면 아래와 같이 구현할 수 있습니다.

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

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