크레인 인형뽑기 게임

2019 카카오 겨울 인턴쉽 기출

January 10, 2025 · 3 min read

#Cpp #Algorithm #Programmers

문제설명 #

죠르디가 만들려는 크레인 인형뽑기 게임은 아래와 같은 규칙을 따른다.¹

게임 화면
- 격자로 이루어진 정사각형 화면.
- 격자 칸에는 인형(숫자로 표현) 또는 빈칸(0)이 있음.
게임 규칙
- 크레인을 좌우로 움직여 지정된 열의 맨 위 인형을 집어 바구니에 담음.
- 바구니에 같은 모양의 인형이 연속으로 쌓이면 터져서 사라짐.
- 빈칸에서는 아무 일도 일어나지 않음.
- 바구니는 무제한 크기.
입력 데이터
- board: 게임 화면 상태를 나타내는 2차원 배열.
- moves: 크레인 작동 위치를 나타내는 배열.
출력
- 크레인 작동 결과 터져서 사라진 인형의 총 개수.

제약 조건

$5 \le N \le 30,\ 1 \le \text{moves} \le 1000$
$0 \le \text{board의 값} \le 100$

문제 나누기 #

주어진 vector를 다시 세로로 한줄씩 관리할 수 있는 형태 변경한다.
moves의 원소의 값에 해당하는 위치의 가장 맨 위의 인형을 pop.
pop한 인형을 바구니에 push
바구니에 서로 겹치는 인형이 있다면 소멸시킨다.

문제 해결하기 #

std::vector<std::vector<int>> vectorToStack(std::vector<std::vector<int>> board);
int getDoll(std::vector<std::vector<int>>& stack_board, int move);
void moveDollToBasket(std::vector<int> &basket, int doll);
void checkDuplicatedDoll(std::vector<int> &basket, int& answer);

각각 1, 2, 3, 4에 해당하는 기능을 함수로 작성하였다. 아래는 전체 코드이다.

전체코드 #

int solution(std::vector<std::vector<int>> board, std::vector<int> moves) {
    int answer = 0;
    std::vector<int> basket;
   	std::vector<std::vector<int>> stack_board = vectorToStack(board);
    for(const auto& move : moves){
        int doll = getDoll(stack_board, move);
        if(doll == 0) continue;
        moveDollToBasket(basket, doll);
        checkDuplicatedDoll(basket, answer);
    }
    return answer;
}

std::vector<std::vector<int>> vectorToStack(std::vector<std::vector<int>> board){
    std::vector<std::vector<int>> vertical_vector;
    for(int x = 0 ; x < board[0].size() ; x++){
        std::vector<int> temp_vector;
        for(int y = 0 ; y < board.size() ; y++){
            if(board[y][x] != 0) temp_vector.emplace_back(board[y][x]);
        }
        vertical_vector.emplace_back(temp_vector);
    }
    return vertical_vector;
}

int getDoll(std::vector<std::vector<int>>& stack_board, int move){
   	if(stack_board[move-1].empty()) return 0;
    int doll = stack_board[move-1][0];
    stack_board[move-1].erase(stack_board[move-1].begin());
    return doll;
}

void moveDollToBasket(std::vector<int> &basket, int doll){
    basket.emplace_back(doll);
}

void checkDuplicatedDoll(std::vector<int> &basket, int& answer){
    if(basket[basket.size()-1] == basket[basket.size()-2]){
        basket.erase(basket.end()-2,basket.end());
        answer += 2;
    }
}

레벨 1의 난도를 가지고 있는 무제라 쉽게 문제 나누기에서 계획한대로 쉽게 나눌 수 있었다. 인덱스 접근을 위해 std::stack<int> 형태가 아닌 바로 std::vector<int> 타입을 사용하였다.

풀이 개선하기 #

개선점

stack을 이용하여 간단하게 변환할 수 있을것
소멸하는 과정에서 push하지 않고 top과 같으면 pop후 answer 값을 증가시킬것

기존에는 std::vector<std::vector<int> 타입을 이용하였으나 이제는 더 간단하고 문제에 의도로 보이는 std::vector<std::stack<int>>를 이용하여 문제 풀이를 개선하여볼 것이다. 또한 2번에서 설명하였듯이 push기능은 소멸되지 않을 때만 작동하도록 변경하겠다.

std::vector<std::stack<int>> vectorToStack(std::vector<std::vector<int>> board){
    std::vector<std::stack<int>> vertical_vector;
    for(int x = 0 ; x < board[0].size() ; x++){
        std::stack<int> temp_stack;
        for(int y = board.size()-1 ; y >= 0 ; y--){
            if(board[y][x] != 0) temp_stack.push(board[y][x]);
        }
        vertical_vector.emplace_back(temp_stack);
    }
    return vertical_vector;
}

스택은 LIFO이므로 y값은 역순으로 순회하도록 하였다.

int getDoll(std::vector<std::stack<int>>& stack_board, int move){
   	if(stack_board[move-1].empty()) return 0;
    int doll = stack_board[move-1].top();
    stack_board[move-1].pop();
    return doll;
}

void moveDollToBasket(std::stack<int> &basket, int doll, int& answer){
    if(!basket.empty() && basket.top() == doll){
        basket.pop();
        answer += 2;
        return;
    }
    basket.push(doll);
}

int solution(std::vector<std::vector<int>> board, std::vector<int> moves) {
    int answer = 0;
    std::stack<int> basket;
   	std::vector<std::stack<int>> stack_board = vectorToStack(board);
    for(const auto& move : moves){
        int doll = getDoll(stack_board, move);
        if(!doll) continue;
        moveDollToBasket(basket, doll, answer);
    }
    return answer;
}

References #

“코딩테스트 연습 - 크레인 인형뽑기 게임,” 프로그래머스 스쿨. https://school.programmers.co.kr/learn/courses/30/lessons/64061 ↩︎