프로그래머스 (크레인 인형뽑기 게임, 2019 카카오 개발자 겨울 인턴십) C++

 

처음 이 문제를 접근할 때 [row][column]이 있을 때 column부터 접근을 해야한다는 고정관념 때문에 새로운 2차원 벡터를 만들어서 해결을 했다. 코드를 보는 사람도 이해하기 힘든 그런 풀이법으로 진행했었다. 분명한 것은 Stack의 개념을 사용하며 알고리즘을 천천히 만든다면 금방 짤 수 있는 코드이다.

 

#include <string>
#include <vector>
#include <iostream>
#include <stack>

using namespace std;

int solution(vector<vector<int>> board, vector<int> moves) {
    int answer = 0;
    stack<int> s;
    
    // 움직인 횟수만큼 for문을 반복시킨다.
    for(int i = 0 ; i < moves.size() ; i++) {
        
        // index라는 변수에 움직인 칸의 번호를 저장시킨다.
        int index = moves[i] - 1;
        
        // board는 square Matrix이므로 해당 size 만큼 반복시킨다.
        for(int j = 0 ; j < board.size() ; j++) {
            
            // 움직인 칸의 제일 윗 번호는 0이 아닌 경우를 처음 만난 경우
            if(board[j][index] != 0) {
                
                // stack이 비어있지 않고 stack의 top이 넣으려는 것과 동일한 경우
                if(!s.empty() && s.top() == board[j][index]) {
                    // 기존 stack의 top을 제거한다.
                    s.pop();
                    // 두 개가 터지므로 2만큼 증가시킨다.
                    answer += 2;
                }
                // 아닌 경우 stack에 push 해준다.
                else {
                    s.push(board[j][index]);
                }
                
                // 움직인 인형은 0으로 최신화를 시켜 없애주는 효과를 낸다.
                board[j][index] = 0;
                break;
            }
        }
    }
    
    cout << answer << endl;
    
    return answer;
}