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

프로그래머스의 크레인 인형뽑기 게임(Lv1) 문제이다.

 

[ 문제풀이 ]

크레인이 주어진 순서에 맞게 인형을 뽑을 때, 터트려져 사라진 인형의 갯수를 구해야 하는 문제이다.

주어진 상황을 코드로 표현하기 위해 사용된 적절한 자료구조부터 정답을 도출하는 과정까지 순차적으로 알아보자.

 

#1. Stack을 이용한 바구니 표현

문제를 풀 때 가장 중요한 부분은 크레인이 인형을 뽑아서 바구니에 담았을 때 바구니에 연속적으로 같은 모양의 인형들이 있는지 없는지를 판단하는 부분일 것이다. 따라서 이 바구니에 인형이 담기는 것과 터지는 상황을 적절하게 구현을 해야 할 것이다. 본인은 이 바구니를 자료구조 'Stack' 을 이용해서 표현하였다.

Stack은 후입선출의 구조를 가진 자료구조로써, 가장 마지막에 담긴 데이터가 가장 먼저 추출되는 성격을 지닌 자료구조이다. 바구니도 Stack과 같은 성격을 가지고 있다. 가장 마지막에 바구니에 담긴 인형일수록 바구니의 가장 위쪽에 있고 가장 먼저 빼낼 수 있기 때문이다.

따라서 본인은 Stack을 이용하여서 표현해주었다.

크레인을 이용해서 인형을 하나 바구니에 넣을 때는 크게 2가지 상황으로 나눌 수가 있다.

1. 바구니가 텅 비어있는 상황

2. 바구니가 텅 비어있지 않은 상황

이렇게 2가지 상황으로 나눌 수 있다. 1번 상황은 어떤 상황을 의미할까 ??

1번 상황이 여러가지가 나올 수 있지만 가장 쉬운 상황으로는 "첫 번째로 인형을 뽑는 상황"이 될 것이다.

첫 번째로 인형을 뽑게 되면, 당연히 첫 번째로 뽑은것이기 때문에 이전에 바구니에 담아놓은 인형이 없을 것이다.

이런 경우에는 그냥 인형을 바구니에 넣어주면 된다. 즉 ! Stack의 push() 함수를 이용해서 뽑은 인형을 넣어주면 된다.

2번 상황일 경우, 우리는 또 2가지 상황으로 나눌 수가 있다.

1. 방금 크레인이 뽑아서 바구니에 넣으려고 하는 인형과 바구니의 가장 위에 있는 인형이 같은 경우

2. 방금 크레인이 뽑아서 바구니에 넣으려고 하는 인형과 바구니의 가장 위에 있는 인형이 다른 경우

이렇게 2가지로 나눌 수 있을 것이다.

만약, 1번 경우를 살펴보자. 넣으려고 하는 인형과 바구니의 가장 위에 있는 인형이 같은 경우이다.

즉 ! 인형을 바구니에 넣는 순간 같은 모양이기 때문에 인형이 터져버리는 상황을 의미하는 것이다.

이 경우에는 정말 간단하게 바구니에 인형을 넣지 않고, 오히려 바구니에서 인형을 하나 빼버리면 된다.

예를 들어서 생각을 해보자. 현재 바구니에 [ 1 2 3 ] 이렇게 인형이 들어있다고 가정해보자.

'3'이 바구니의 가장 위쪽에 있는 인형이라고 가정해보자. 이 때, 크레인이 '3'번 인형을 뽑아서 바구니에 넣는다면 바구니의 상황은 [ 1 2 3 3 ] 이 될 것이다. 이 때, '3 3'은 만나서 터지게 될 것이다. 터지게 되면 결국 바구니는 [ 1 2 ] 의 상황으로 남게 될 것이다.

즉 ! [ 1 2 3 ] 이였던 바구니가 [ 1 2 ] 로 바뀌게 되는 것이다. 이렇게 바꾸기 위해서는 가장 위에 있는 원소를 없애주기만 하면 된다. 즉 ! Stack의 pop() 연산을 통해서 같은 인형끼리 만나서 터지는 상황을 표현할 수 있다.

이런식으로 Stack을 이용해서 바구니를 표현할 수 있다.

 

#2. 크레인 인형뽑기

#1에서 정답 도출에 더 가까운 단계를 진행했고 이 부분에서는 인형을 바구니에 넣기 전에 인형을 어떻게 뽑을 것인지에 대해서 이야기해보자. 인형을 뽑는 것은 간단하다. 주어진 열에서 모든 행을 탐색하면서 인형이 있다면 그 인형을 가져오면 된다. 주의할 것은 "뽑을 인형이 없는 경우" 와 "인형을 뽑았으면, 해당 인형이 있던 좌표는 인형이 없는 칸으로 만들어 주는 것" 이다. 이 부분만 주의한다면 인형을 뽑는 부분을 표현할 수 있다.

 

[ 소스코드 ]

#include <string>
#include <vector>
#include <stack>
using namespace std;
 
int Move_Crain(vector<vector<int>> &MAP, int Pos)
{
    int Result = 0;
    int x = 0;
    while (x < MAP.size())
    {
        if (MAP[x][Pos] != 0)
        {
            Result = MAP[x][Pos];
            MAP[x][Pos] = 0;
            break;
        }
        x++;
    }
    return Result;
}
 
int solution(vector<vector<int>> board, vector<int> moves) 
{
    int answer = 0;
    stack<int> Pocket;
    for (int i = 0; i < moves.size(); i++)
    {
        int Pos = moves[i] - 1;
        int Pick = Move_Crain(board, Pos);
        
        if (Pick == 0) continue;
        if (Pocket.size() == 0) Pocket.push(Pick);
        else
        {
            int Top = Pocket.top();
            if (Pick == Top)
            {
                Pocket.pop();
                answer += 2;
            }
            else Pocket.push(Pick);
        }
    }
    return answer;
}