[2019 카카오 개발자 겨울 인턴십] 크레인 인형뽑기 게임(C++)

크레인 인형뽑기 게임

 

코딩테스트 연습 - 크레인 인형뽑기 게임

 

문제 설명

 

 - 위 그림처럼 각 인형들이 가장 아래 칸부터 차곡 차곡 쌓여 있다.

 

 - 사용자는 크레인을 좌우로 움직여 멈춘 위치에서 가장 위에 있는 인형을 집어 올릴 수 있다.

 

 - 집어 올린 인형은 바구니에 가장 아래 칸부터 쌓이게 된다.

 

 

 

 

 - 만약 같은 모양의 인형 두 개가 바구니에 연속해서 쌓이게 되면 두 인형은 터뜨려지면서 바구나에서 사라지게 된다.

 

 - 크레인을 모두 움직인 후 바구니에서 사라진 인형의 개수를 구하라.

---

 

입력 값

 

 - 게임 화면의 격자 상태(인형의 값)가 담긴 2차원 배열 board( board의 크기는 5x5 이상 30x30 이하. )

 

 - 인형을 잡기 위해 크레인을 작동시킨 위치가 담긴 배열 moves( 1 <= moves.size() <= 1,000 )

 

 - board에는 0 이상 100 이하의 정수가 담겨져 있고, 0은 빈칸 1에서 100의 숫자는 각 인형의 모양을 의미한다.

   같은 숫자는 같은 모양의 인형을 나타낸다.

 

 

---

예제

 

 

---

문제 분석

 

 - moves의 값을 순회하면서, 해당 위치 가장 위에 있는 인형 값을 구하고, 바구니에 넣으면 된다.

 

 - 바구니에 넣을 때 가장 위에 있는 인형과 크레인으로 가져온 인형을 비교하여 같을 경우 제거 한다.

 

 - 바구니는 가장 먼저 들어온 인형이 맨 밑에, 가장 나중에 들어온 인형이 맨 위에 쌓이는 구조이기 때문에

   Stack을 사용한다.

 

---

 

소스코드(C++)

#include <bits/stdc++.h>

using namespace std;

int solution(vector<vector<int>> board, vector<int> moves) {
    int answer = 0;
    
    // 크레인으로 가져온 인형을 담을 바구니
    stack<int> bags;
    
    // 크레인을 움직이는 moves 값 순회
    for(auto m : moves)
    {
        for(int i=0;i<board.size();i++)
        {
       		// 해당 위치의 값이 0이 아닌 경우
            // ==> 해당 위치에 인형이 존재한다.
            if(board[i][m-1]!=0)
            {
                int dollNumber = board[i][m-1];
                if(bags.empty())
                    bags.push(dollNumber);
                else if(bags.top()==dollNumber)
                {
                    bags.pop();
                    answer+=2;
                }
                else
                    bags.push(dollNumber);
                    
                board[i][m-1]=0;
                
                break;
            }
        }
    }
    
    
    return answer;
}