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

문제  : Level1 크레인 인형 뽑기 게임 

[ 문제출처 ]  https://programmers.co.kr/learn/courses/30/lessons/64061

 

 

[ 문제풀이 ]

 

이 문제는 친절하게도 Stack 을 사용하게끔 해당 문제의 그림에서도 유도해주었다.

 

크레인을 작동시킬 위치가 담긴 배열 moves 에서 차례로 하나씩 값을 꺼내어

해당 위치의 열에서 가장 위에 있는 값을 스택에 넣어 주면 된다.  이 부분을 따로 함수로 구현해 주었다

 

하지만 2가지 상황이 존재한다.

1. 해당 위치의 열에  뽑을 인형이 없는 경우   -->    -1 을 Return 

2. 뽑을 인형이 존재   -->  해당 자리에 0을 넣고 인형의 모양을 의미하는 숫자를 Return 

 

 

 바구니에 담는 과정에서 터지는 상황을 생각해보자  아니, 

 일단 바구니에 터지지 않고 그냥 담을 수 있는 상황을 생각 해보자

 

 

1. 일단 바구니에 아무것도 없는 경우

2. 바구니에 인형이 존재 하지만  인형의 모양을 의미하는 숫자가 다른 경우

그 외에는 바구니에 담는 과정에서 무조건 터지게 된다.

 

터지는 과정에서 2개씩 터지므로 answer += 2 를 해주었다.

 

 

[ 소스 코드 ]

 

#include <string>
#include <vector>
#include <stack>
using namespace std;
// 해당 열의 가장 위에 있는 인형을 반환한다.
int go(vector<vector<int>>& board, int col) {
    int row = 0, ans = 0, size = board.size();
    while (row != size && board[row][col] == 0) row++;
    if (row == size) return -1;
    ans = board[row][col];
    board[row][col] = 0;
    return ans;
}
int solution(vector<vector<int>> board, vector<int> moves) {
    int answer = 0;
    stack<int> s;
    for (int now : moves) {
        int doll = go(board, now - 1);
        if (doll == -1) continue;
        if (s.empty() || s.top() != doll) s.push(doll);
        else {
            if (!s.empty()) s.pop();
            answer += 2;
        }
    }
    return answer;
}