[C++] 프로그래머스 크레인 인형뽑기 게임

https://school.programmers.co.kr/learn/courses/30/lessons/64061

프로그래머스

풀이

구현 문제입니다.

스택 자료구조 및 방문 처리를 통해 문제를 해결할 수 있습니다.

 

모든 moves에 대해, 선택한 열의 가장 위에 인형이 존재한다면 스택의 인형과 비교합니다.

이때, 스택에 인형이 존재하면서 가장 위의 인형과 현재 인형(n)이 같다면 answer에 2를 추가해주고 들어있던 인형을 제거해줍니다. 같지 않은경우 push만 해줍니다. 마찬가지로 스택이 비어있는 경우 또한 push만 해줍니다.

 

board에서 빈칸 처리 후 break를 사용해 다음 move로 넘어갑니다.

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

using namespace std;

int solution(vector<vector<int>> board, vector<int> moves) {
    int answer = 0;
    stack<int> stk;
    
    for (auto i : moves) {
        for (int row = 0; row < board.size(); row++) {
            /* 
                인형이 존재한다면 
                스택에 인형이 있다면 비교, 같은경우 +2 & 가장 위 인형 제거, 아니면 그냥 넣기
                없다면 그냥 넣기 
                빈칸 처리 & 다음 move
            */
            if (board[row][i-1]) {
                int n = board[row][i-1];
                if (!stk.empty()) {
                    if (n == stk.top()) {
                        answer += 2;
                        stk.pop();
                    }
                    else
                        stk.push(n);
                }
                else {
                    stk.push(n);
                }
                // 빈칸 처리 & 다음 move
                board[row][i-1] = 0;
                break;
            }
        }
    }
    return answer;
}