(카카오 인턴십) 크레인 인형뽑기 게임

 

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

 

이 문제도 어려운 문제는 아닙니다. 그냥 직관적으로 접근해서 문제 요구에 따라 풀면 되는 문제입니다. 

 

여기서 중요한 개념이 스택이라고 생각합니다. stack STL을 사용해서 push(), pop()을 해도 되지만

 

직접 stack을 간단하게 구현했습니다. 완벽한 스택이라고 할 수는 없고, 스택의 원리?를 이용한 배열이라고 할 수 있습니다. 

 

/*
문제 해결 방안
 
(1) 배열에 벡터의 정보를 그림과 같이 넣는다 (보기 편하기 위함)
(2) 스택을 만든다. 
(3) 크레인에 잡힌 인형과 스택 top에 쌓인 인형이 같으면 +2 d
    같지 않으면, 인형을 top에 쌓는다.
(4) 인형은 하나만 뽑혀야 하므로 하나 뽑고 break;
*/
#include <string>
#include <vector>
 
using namespace std;
int myStack[1050];
 
int solution(vector<vector<int>> board, vector<int> moves) {
    int top = 0;
    int arr[35][35];
    int n = board[0].size();
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            arr[i][j] = board[i][j];
        }
    }
 
    int answer = 0;
 
    for(int k = 0; k < moves.size(); k++){
        for(int i = 0; i < n; i++){ //위에서부터 검사 
            if(arr[i][moves[k]-1]) { //만약 인형이 있으면 
                if(myStack[top-1] == arr[i][moves[k]-1]){ //인형이 스택(바구니) top과 같으면
                    answer += 2; 
                    myStack[top-1] = 0;
                    top--;
                }
                else{
                    myStack[top] = arr[i][moves[k]-1];
                    top++;
                }
                arr[i][moves[k]-1] = 0;
                break;
            }
        }
    }
    return answer;
}

 

그럼 20000~~~