크레인 인형뽑기 게임 (프로그래머스)

크레인으로 옮겨진 인형들은 바구니에 차곡차곡 쌓이기 때문에 스택을 이용하면 편하다. 

 

접근 방법은 다음과 같다.

• 우선 크레인을 특정 인덱스에 있는 인형을 집어야 한다.

• 특정 인덱스인 그 열에서 첫번째 행부터 마지막 행까지 반복하며 인덱스 접근으로 인형을 찾는다.

• 인형이 있는경우 반복문을 빠져나오고 그 자리를 빈공간으로 만들어 준다.

• 집어넣기 전에, 바구니에 마지막으로 넣은 인형이 현재 크레인이 집은 인형과 같다면 두 인형은 터뜨려져야 하므로 바구니에서 인형을 꺼내고 크레인이 집은 인형은 바구니에 넣지 않는다. 

• 바구니가 비어 있거나 바구니에 마지막으로 넣은 인형과 다르면 크레인이 집은 인형을 바구니에 넣는다.

코드는 다음과 같다.

#include <vector>
#include <stack>   // STL 스택 사용을 위함

using namespace std;

int solution(vector<vector<int>> board, vector<int> moves) 
{
    int answer = 0;
    stack<int> s;
    for(const auto iter : moves) 
    {
        int move = iter - 1; // 크레인이 집어야 하는 인덱스 위치 (열)
        // 그 열의 첫번째 행부터 마지막 행까지 반복한다.
        for(int i = 0; i < board.size(); ++i) 
        {   
            // 만약 인형이 있다면
            if(board[i][move] != 0)
            {
                // 바구니가 빈 경우 인형을 집어 넣는다.
                if(s.empty()) s.push(board[i][move]);
                else 
                {
                    // 바구니가 비어있지 않은 경우
                    // 마지막으로 넣은 인형이 크레인이 집은 인형과 같은 경우
                    if(s.top() == board[i][move])
                    {
                        // 바구니에서 인형을 꺼내고 터뜨린 인형 수를 기록한다.
                        s.pop();
                        answer += 2;
                    }
                    // 아니면 그냥 바구니에 넣는다.
                    else s.push(board[i][move]);
                }
                // 크레인이 집은 인형의 자리는 빈공간으로 채운다.
                board[i][move] = 0;
                break;
            }   
        }
    }
    return answer;
}