프로그래머스 - lv1 크레인 인형뽑기 게임

크레인 인형뽑기 게임

문제는 프로그래머스에서 확인 할 수 있다.


✔ 접근방법

스택을 이용한다.

  1. 기계에서 인형을 선택한다.
  2. 선택한 인형을 스택에 넣는다.
  3. 스택의 맨 위 인형과 현재 들어올 인형이 같다면, pop() 후 count 한다.

✔ 코드

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

using namespace std;

int choose(vector<vector<int>>& board, int move); // 뽑기기계에서 인형을 뽑는 함수 

int solution(vector<vector<int>> board, vector<int> moves) {
    int answer = 0;
    int cur = 0;
    int pop_cnt = 0;

    stack<int> s;

    for( int i=0; i<moves.size(); i++){
        cur = choose(board, moves[i]-1); // moves의 값이 1부터 시작하기 때문에 -1 필요
        // printf("[check] %d", cur);

        if( cur == 0 ) continue;
        
        if(s.empty()){
            s.push(cur);
        }
        else{
            if( s.top() != cur ){
                s.push(cur);
            }
            else{ // 스택의 맨 위 인형과 현재 들어올 인형이 같다면, 스택에 푸쉬하지 않는다.
                s.pop();
                pop_cnt++;
            }
        }
    }

    answer = pop_cnt*2;
    // printf("\n%d\n", answer);

    return answer;
}

int choose(vector<vector<int>>& board, int move){
    /* c++에서는 참조자를 사용할 수 있음. 될 수 있으면 포인터 대신 참조자를 사용한다. */
    int ret=0;

    for ( int i=0; i<(board)[move].size(); i++ ){
        if( (board)[i][move] != 0 ){
            ret = (board)[i][move];
            (board)[i][move] = 0;
            return ret;
        }
    }
    return 0;
}

int main(void){

    vector<vector<int>> board = {{0,0,0,0,0},{0,0,1,0,3},{0,2,5,0,1},{4,2,4,4,2},{3,5,1,3,1}};
    vector<int> moves = {1,5,3,5,1,2,1,4};

    solution(board,moves);

    return 0;
}



☝ 팁

  • c스타일에 익숙하다 보니 포인터를 함수의 인자로 사용해서 call-by-reference를 시도했었는데, c++에는 포인터로 인해 야기되는 문제를 방지하기 위해 참조자(&)가 존재한다. 될 수 있으면 포인터보다는 참조자를 먼저 사용하는 것에 익숙해지는 것이 좋다.
  • vector, stack 에 대한 이해

👍 참고 사이트

프로그래머스

좋은 웹페이지 즐겨찾기