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

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

풀이

vector 컨테이너를 사용해 스택 자료구조를 흉내냈다.

return해야 될 것은 크레인 작동이 끝난 후 터트려져 사라진 인형의 개수.

 

- 스택에 push할 경우

1. 스택이 비어있다

2. 스택의 top이 크레인으로 끄낸 인형과 다르다.

 

- 스택에서 pop할 경우

1. 크레인으로 끄낸 인형이 스택의 top과 같다.(answer를 2개씩 증가)

 

#include <string>
#include <vector>
// 격자의 상태가 담긴 2차원 배열 board
// 크레인의 위치 배열 moves(1~1000)
// 사라진 인형의 개수를 return
// 0~100 인형의 종류

using namespace std;

int solution(vector<vector<int>> board, vector<int> moves) {
    int answer = 0;
    vector<int> basket;
    vector<int>::iterator cIter;
    int doll;
    
    // 크레인의 움직임
    cIter = moves.begin();
    while(cIter!=moves.end())
    {
        // 보드의 행 검사
        for(int i=0; i<board.size(); i++)
        {
            doll = board[i][*cIter - 1];
            if(doll != 0)
            {
                // 바구니와 비교
                if(!basket.empty())
                {
                    if(basket.back() == doll)
                    {
                        basket.pop_back();
                        answer += 2;
                    }
                    else
                    {
                        basket.push_back(doll);
                    }
                }
                else
                {
                    basket.push_back(doll);
                }
                board[i][*cIter - 1] = 0;
                break;
            }
        }
        // 다음 움직임
        cIter++;
    }
    return answer;
}