프로그래머스 - 크레인 인형뽑기 / C++

문제 링크 : programmers.co.kr/learn/courses/30/lessons/64061

코딩테스트 연습 - 크레인 인형뽑기 게임

 

아이디어 : 바구니가 LIFO(Last In First Out) 이므로 스택을 통해 구현한다. 배열은 n x n 형태이고 윗줄부터 차례대로
0, 1, 2행이다. 크레인으로 인형을 뽑을때는 해당 열에서 0이 아닌 것을 뽑으므로 col이라는 열을 담당하는 변수를 선언해서 for문을 돌려준다.
인형이 있다면 각자 1, 2, 3.. 의 순서로 인형의 번호가 있으므로 board[i][col]이 0인지 아닌지 판단해서 바구니에 넣는다. 만약 바구니가 비어있거나 바구니에서 가장 위에 있는 인형과 현재 뽑은 인형이 다르다면 그냥 인형을 넣으면 되고 그렇지 않다면 같은 인형이 터지고 +2 카운트를 해준다. 이를 조건식으로 구현한다.

 

시행착오 : 처음엔 인형을 모두 넣고 다시 st 스택을 for문으로 돌려서 판단하려 했지만 스택을 반복문과 함께 사용하기 어려울 뿐만 아니라, 인형이 3 2 1 1 2 4 5 와 같은 경우 1, 1이 터진 다음 2, 2를 판단하기 어려워 인형을 넣음과 동시에 판단하는 코드로 수정하였다.

 

<코드>

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int solution(vector<vector<int>> board, vector<int> moves) {
    stack<int> st;
    int answer = 0;
    int tmp;

    for(int j=0;j<moves.size();j++){
       for(int i=0;i<board.size();i++){
            int col = moves[j]-1;
            if(board[i][col] != 0){
                if(!st.empty() && st.top() == board[i][col]){
                    answer += 2;
                    st.pop();
                }
                else{
                    st.push(board[i][col]);
                }
                
                board[i][col] = 0;   
                break;
            }
         }
    }
    
    return answer;
}