크레인 인형뽑기 게임

들어가는 말

크레인 인형뽑기 게임은 2019 카카오 개발자 겨울 인턴십 문제다. 인형이 들어간 2차원 벡터 board가 주어지고 어느 번째 인형을 뽑는지에 대한 moves가 1차원 벡터로 주어진다. 우리가 할 일은 moves 위치에서 맨 먼저 있는 인형을 뽑아 옮기고 만일 앞뒤로 인형이 동일하면 지워주는 것이다. 인형을 총 몇 개 지웠는지를 반환해주면 된다.

코드 설명

문제를 총 두 개로 나눠서 해결했다. 새로운 벡터 v를 만들어서 그곳에 인형을 옮겨주는 반복문 하나, v에서 같은 인형을 검색해 지워준 후 answer을 증가하는 반복문 하나.

첫 번째 반복문에서는 moves의 크기만큼 돌려주면서 moves의 값을 current에 넣어준다. 내부 반복문은 주어진 current의 위치를 중심으로 행을 증가시키며 제일 윗 부분을 찾아준다. 만일 값이 있다면 v에 넣어주고 넣어준 값은 0으로 돌려준다. 마지막으로 break를 하여 뒷 부분이 들어가지 않게 한다. 첫 번째 반복문이 끝난다면 v에는 moves가 원하는 만큼의 인형이 들어가 있다.

두 번째 반복문에서는 v에 있는 인형 값들을 비교해주면서 answer을 구해주는 것이다. v의 크기 만큼 돌려주면서 만일 현재의 값과 그 앞의 값이 같으면 answer에 2를 더해주고(인형은 두 개 지워지니까) 현재의 값과 그 앞의 값을 지워준다(i를 1부터 시작해서 i-1을 비교해주는 걸로 해줬다). v의 값 두 개가 지워졌으니까, 뒤에 있는 값들이 자연스럽게 지워진만큼 당겨질 거다. 때문에 i에다가 2를 빼줘서 당겨진 위치에서 다시 검사를 해줘야 한다.

주의할 점은 첫 번째 반복문의 두 번째 for문에서 board.size()까지 돌려줘야 한다는 점이다. 문제의 예시가 5x5라서 5까지만 돌려줬더니 틀렸다고 나왔다. 예시로는 NxN 크기의 정사각형이 주어진다.

코드

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

int solution(vector<vector<int>> board, vector<int> moves) {
    int answer = 0;
    int current = 0;
    vector<int> v;
    
    
    for(int i=0; i<moves.size(); i++){
        current = moves[i];
        for(int j=0; j<board.size(); j++){
            if(board[j][current-1] != 0){
                v.push_back(board[j][current-1]);
                board[j][current-1] = 0;
                break;
            }
        }
    }
    
    
  for(int i=1; i<v.size(); i++){
        if(v[i] == v[i-1]){
            answer = answer + 2;
            v.erase(v.begin() + i);
            v.erase(v.begin() + i-1);
            i = i - 2;
        }
    }
    
    return answer;
}

P.s

v를 벡터가 아닌 스텍을 이용하면 더 쉽게 풀 수 있다.