[2019 카카오 개발자 겨울 인턴십] 크레인 인형뽑기 게임 (Level 1)

 

내가 해결한 방법은 다음과 같다.

1. 각 column의 높이를 담는 배열을 만든다. ( O(N^2) 이긴하나 case가 30 x 30이므로 900번만 계산하면됨 )

2. 1에서 만든 배열을 바탕으로 board에서 위치를 찾고 stack에다 담는다.

3. moves만큼 반복문을 돌면서 높이는 계속 갱신해주고 stack의 top과 뽑은 인형을 비교해서 stack에 push하거나 pop한다. pop할때는 ans에 2만큼 추가해준다.

 

stack만 알고있다면 알고리즘에 대해 따로 공부하지 않았어도 풀어볼만한 문제같다. 다만 비교적 코드수가 많이나와서 디버깅하는데 애를 꽤 먹었다. 실전에서 풀게된다면 디버깅 기능없는 웹 ide로 풀어야할텐데 생각보다 실전에서 풀기 힘들것 같다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#include <string>
#include <stack>
#include <cstdlib>

using namespace std;

vector<vector<int>> board = {
    {0, 0, 0, 0, 0},
    {0, 0, 1, 0, 3},
    {0, 2, 5, 0, 1},
    {4, 2, 4, 4, 2},
    {3, 5, 1, 3, 1}
};

vector<int> moves = { 1, 5, 3, 5, 1, 2, 1, 4 };

int col = board.size(); 
int* heightCheck = new int[col];

void init() {

    for (int i = 0; i < col; i++) {
        heightCheck[i] = 0;
    }

    // 각 column별 높이 체크
    for (int i = 0; i < col; i++) {
        for (int j = 0; j < col; j++) {
            if (board[j][i] != 0) {
                heightCheck[i] = col - j;
                j = 0; break;
            }
        }
    }
}

int solution() {
    int ans = 0;

    stack<int> st;

    for (int i = 0; i < moves.size(); i++) {

        int top = 0;
        if (!st.empty()) top = st.top();

        int idx, doll = 0;
        if (heightCheck[moves[i] - 1] != 0) {
            idx = col - heightCheck[moves[i] - 1];
            doll = board[idx][moves[i] - 1];
        }

        if(heightCheck[moves[i]-1] != 0)
            heightCheck[moves[i]-1] = heightCheck[moves[i]-1] - 1;

        if (doll != 0) {
            if (top == doll) {
                st.pop(); ans += 2;
            }
            else {
                st.push(doll);
            }         
        }

    }

    return ans;
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    init();
    cout << solution();

    return 0;
}