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

오늘부터 카카오 기출문제 풀이 형벌에 처하도록 하겠다...
어려운문제를 풀어야 실력이 늘지 않을까? 싶다...
이번문제의 난이도는 하 난이도로 stack 자료구조를 쓸 줄 안다면, 전혀 어렵지 않은문제였다.

구현과정은 2가지로

1. 그래프를 만드는과정 makegraph()
2. 그래프를 가지고 stack에 넣는과정으로 표현했다.

board의 최대 size가 30이므로 열대로 넣기 위해서 1,2,3,4,,,,30이므로 graph[31]로 만들었다.

참고로 중간에 segfault 오류가 떳는데, 문제를 보면
만약 인형이 없는 곳에서 크레인을 작동시키는 경우에는 아무런 일도 일어나지 않습니다.
라는 중요한 단서를 놓쳤다.

만약 graph가 비어있는데 접근하면 segfault 오류가 뜨므로,
graph가 항상 size가 1이상인지 판단하는 if조건문을 처리해주기만 한다면, 어렵지 않은 문제였다.
if(mygraph[t].size()>0)

#include <string>
#include <vector>
#include <iostream>
#include <stack>
using namespace std;
vector<int> mygraph[31];
 int board_size = 0;

void makegraph(vector<vector<int>> &board){
    for(int i=0;i<board.size();i++){
        for(int j=0;j<board.size();j++){
            int tmp = board[j][i];
            if(tmp>0){
                mygraph[i+1].push_back(board[j][i]);
            }
        }
    }
}

int solution(vector<vector<int>> board, vector<int> moves) {
    int answer = 0;
    vector<int> graph[31];
    board_size = board.size();
    
    makegraph(board);
    
    stack <int> s;
    for(int i=0;i<moves.size();i++){
        int t = moves[i];
        if(mygraph[t].size()>0){
           int tmp = mygraph[t][0];
           mygraph[t].erase(mygraph[t].begin());
            s.push(tmp);
            if(s.size()>1){
                int t1=s.top();
                s.pop();
                int t2 = s.top();
                if(t1==t2){
                    answer++;
                    answer++;
                    s.pop();
                }else{
                    s.push(t1);
                }            
            }
        }
    }
    
    return answer;
}