[프로그래머스] Lv.1 크레인 인형뽑기 게임 c++

https://school.programmers.co.kr/learn/courses/30/lessons/64061

프로그래머스

 

2019 카카오 개발자 겨울 인턴십에 나온 문제입니다.

크레인 인형뽑기 게임을 모바일 게임으로 구현하려고 합니다.

 

조건

1. N x N 크기의 격자판(board)에 인형들이 쌓여 있고, 각 칸은 숫자로 표현됩니다. 0은 빈 칸, 1~100은 각각 다른 인형 모양을 나타냅니다.
2. 사용자는 주어진 이동 명령(moves)에 따라 크레인을 특정 열로 이동시켜 가장 위에 있는 인형을 집어 바구니에 넣습니다.
3. 바구니에 같은 모양의 인형이 연속으로 쌓이면 두 인형이 사라지며 점수를 획득합니다.
4. 크레인이 빈 칸에서 작동하면 아무 일도 일어나지 않습니다.

크레인을 이동시키는 명령 배열(moves)을 따라 인형을 뽑고, 터뜨려서 사라진 인형의 개수를 반환하세요.

풀이 방법

이 문제는 스택을 이용하여 해결했습니다.

우선, 입력으로 주어진 board는 행(row) 기준으로 저장된 2차원 배열입니다.

이를 열(column) 단위로 처리하기 위해 새로운 배열 tmpstack에 열(column) 형식으로 변환하여 저장했습니다.

변환 과정에서는 각 열의 요소를 역순으로 쌓아, 스택처럼 처리할 수 있도록 했습니다.

 

다음으로, 크레인의 이동 명령을 담고 있는 moves 배열을 순회하며 크레인을 작동시켰습니다.

각 명령에 따라 해당 열의 가장 위에 있는 인형을 꺼내(pop) 바구니 역할을 하는 basket 스택에 넣었습니다.

이때, basket의 맨 위에 있는 인형(top)과 방금 추가된 인형이 동일하다면 같은 인형은 basket에서 제거하고, 제거된 인형의 개수를 점수(answer)에 더했습니다. 

 

풀이 코드

#include <string>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;
stack<int> basket;
vector<vector<int>>tmpstack;
int solution(vector<vector<int>> board, vector<int> moves) {
    int answer = 0;
    for(int i=0; i<board.size(); i++){
        vector<int> tmp;
        for(int j=0; j<board.size(); j++){
            if(board[j][i]!= 0) tmp.push_back(board[j][i]);
        }
        reverse(tmp.begin(), tmp.end());
        tmpstack.push_back(tmp);
    }
    
    for(int i : moves){
        if(tmpstack[i-1].size() != 0){
            int picknum = tmpstack[i-1].back();
            tmpstack[i-1].pop_back();

            if(!basket.empty() && basket.top() == picknum){
                basket.pop();
                answer+=2; //사라지는 인형 기준
            }
            else basket.push(picknum);
        }
    }
    return answer;
}