2019 카카오 개발자 겨울 인턴십 : 크레인 인형 뽑기 게임(C++)

programmers.co.kr/learn/courses/30/lessons/64061

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

해당 문제에 관한 내용은 위의 사이트에 들어가면 자세히 확인할 수 있다.

 

풀이법

1) 아래에서 부터 쌓인다는 특징을 기억해야 한다. 같은 열 기준으로 행의 값이 커질 수록 0이 아닌 item이 있을 것이니 이를 for문을 이용해서 확인해야 한다.

2) 뽑고 난 후 원래 배열에서 해당 칸의 값은 0으로 초기화 해주어야 한다.

3) 2개가 연속된 경우 지우는 것을 구현하기 위해 stack을 활용하면 문제를 쉽게 해결할 수 있다.

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

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

주의사항)

moves의 값이 1,2,3,4,5로 나온 것으로 보아 0번부터 시작하는 index를 맞춰주기 위해서는 -1을 해주어야 했다.

행의 크기를 구하기 위해서 board[0].size()를 활용해 주었다.

1) 값이 존재하는데 stack이 빈 경우에는 stack에 값을 넣고, 해당 배열의 원래 값을 0으로 초기화 시킨 후 break

2) 스택의 맨 위 값과 새로 넣을 값이 같은 경우 answer를 2 증가시키고, stack을 pop한 후, 0으로 초기화 & break

3) 스택의 맨 위 값과 새로 넣은 값이 같지 않은 경우, stack에 값을 넣고 해당 배열의 원래 값을 0으로 초기화 시킨 후 break

 

-> 중요한 부분은 break다. 이미 0이 아닌 값을 찾은 경우, 다른 행을 볼 필요가 없으므로 break를 해주는 것이 옳다. 이를 묶어서 break 하나로 써 클린 코드를 짤 수 있었지만, 직관성을 높이기 위해 나누어 써 주었다.