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

문제 위치 : https://school.programmers.co.kr/learn/courses/30/lessons/64061

프로그래머스

 

데이터를 잘 가공해주면 쉽지만 그렇지 않다면 오래 걸리는 문제이다.

이유는 board에 빈칸을 나타내는 0의 값이 있기 때문이며 수평마다 vector로 저장되어 있지만 문제의 처리는 수직마다 관리해주어야 하기 때문이다.

 

따라서 크레인을 동작하기 이전 최상단의 인형이 각 위치를 나타내는 벡터의 back에 두도록 가공해주었다.

 

이후는 문제에서 제시된대로 구현해주면 된다.

 

인형을 떨어트리는 칸을 따로 스택을 구현할까 하였지만 vector의 최상단을 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> stack_box;
    vector<vector<int>> dolls(N);

    // 인형 박스를 설정: dolls[i]는 각 열에 대한 인형 목록 (아래에서 위로)
    for (int i = 0; i < N; i++) {
        for (int j = N - 1; j >= 0; j--) { // 바닥부터
            if (board[j][i] != 0) { // 인형이 있으면
                dolls[i].push_back(board[j][i]);
            } else {
                break; // 더 이상 인형이 없으면 멈추기
            }
        }
    }

    // moves 배열을 처리
    for (int move : moves) {
        if (!dolls[move - 1].empty()) { // 해당 열에 인형이 있으면
            int doll = dolls[move - 1].back(); // 해당 열의 최상단 인형
            dolls[move - 1].pop_back(); // 해당 열에서 인형 제거

            if (stack_box.empty()) { // stack이 비었으면 인형을 넣는다
                stack_box.push_back(doll);
            } else { 
                if (stack_box.back() == doll) { // 같은 인형이 나오면 터진다
                    answer+=2; // 터트린 횟수 증가
                    stack_box.pop_back(); // 터트린 인형 제거
                } else { // 같은 인형이 아니면 넣는다
                    stack_box.push_back(doll);
                }
            }
        }
    }

    return answer;
}