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

Lv.1 크레인 인형뽑기 게임

📌 문제

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

프로그래머스

 

📌 풀이

크레인 인형뽑기 게임을 위한 로직을 짜는 문제이다.

n*n 크기의 정사각 보드에 있는 인형들을 뽑아 바구니에 담고 같은 인형 두 개가 연속으로 담겨있으면 없어지는 게임을 만들어야 한다.

이때, 없어지는 인형의 개수를 정답으로 반환한다.

 

그림과 같은 정사각 보드를 2차원 벡터 board로 나타내면 아래의 표처럼 나타난다.

크레인은 위에서 아래로 인형이 있는곳까지 내려가기 때문에 한번 뽑을때마다 해당 열에서 인형을 마주칠때까지 행을 탐색해야 한다.

이렇게 탐색을 진행하면 빈 공간들도 반복적으로 탐색하게 되기 때문에 효율적이지 않다.

 

따라서 효율적인 탐색을 위해 인덱스 벡터 idx를 만들어 각 열의 맨 위에 있는 인형의 위치를 저장해주어야 한다.

이때 맨 위의 인형의 위치는 n - 해당 열에 있는 인형의 개수이기 때문에 idx 벡터를 n으로 초기화해주고 인형을 마주칠때마다 1씩 빼주면 된다.

int n = board.size();

vector<int> idx(n, n);

for(int i=0;i<n;i++) {
    for(int j=0;j<n;j++) {
        if(board[i][j] != 0) {
            idx[j]--;
        }
    }
}

 

크레인이 집은 인형은 그림과 같이 바구니(basket)에 담기고 같은 종류의 인형 두 개가 연속적으로 쌓이면 두 인형이 없어진다.

 

idx 벡터에 저장된 위치를 참고해 크레인을 작동시킨 위치의 인형을 뽑아준다.

벡터가 0부터 시작하기 때문에 크레인 작동위치(moves[i])에 -1을 해주어야 정확한 위치를 찾을 수 있다.

 

이때 idx의 값은 board의 행을, moves의 값은 board의 열을 가리키기 때문에 board[idx[moves[i]-1]][moves[i]-1]에 있는 인형을 basket에 push_back() 해줘야 한다.

인형을 뽑으면 이제 그 자리에는 인형이 없으므로 값을 0으로 바꿔주고, 다음 행을 가리킬 수 있도록 idx에 +1을 해준다.

 

만약 idx의 값이 n과 같으면 인형이 없다는 뜻이므로 바구니에 인형을 담지 않는다.

vector<int> basket;

if(idx[moves[i]-1] != n) {
    basket.push_back(board[idx[moves[i]-1]][moves[i]-1]);
    board[idx[moves[i]-1]][moves[i]-1] = 0;
    idx[moves[i]-1]++;
}

 

basket의 맨 마지막에 담긴 인형과 맨 마지막-1에 담긴 인형을 비교하고 같으면 두 인형을 pop_back() 하고 answer에 2를 더해준다.

if(basket[basket.size()-1] == basket[basket.size()-2]) {
    answer += 2;
    basket.pop_back();
    basket.pop_back();
}

 

📌 전체 코드

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> board, vector<int> moves) {
    int answer = 0;
    int n = board.size();
    
    vector<int> idx(n, n);
    vector<int> basket;
    
    for(int i=0;i<n;i++) {
        for(int j=0;j<n;j++) {
            if(board[i][j] != 0) {
                idx[j]--;
            }
        }
    }

    for(int i=0;i<moves.size();i++) {
        if(idx[moves[i]-1] != n) {
            basket.push_back(board[idx[moves[i]-1]][moves[i]-1]);
            board[idx[moves[i]-1]][moves[i]-1] = 0;
            idx[moves[i]-1]++;
        }
        if(basket[basket.size()-1] == basket[basket.size()-2]) {
            answer += 2;
            basket.pop_back();
            basket.pop_back();
        }
    }
    
    return answer;
}

 

📌 결과

제출 결과 무던히 통과했다 👍👍