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

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

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

 

알고리즘)

1. 스택을 정의한다.

=> 마지막에 넣은 원소를 꺼내 비교해야 하기 때문에 스택을 정의함

2. check 라는 변수를 정의한다.

=> moves의 원소를 하나씩 꺼내 board의 열에 해당하는것을 표현할수 있도록 재정의함.

3. board 배열안 원소가 0이 아닐경우 (비어있지 않는 경우) 비교함

=> 스택이 비어있는 초기의 경우 , board 에서 moves 에 해당되는 원소를 스택에 저장한다.

그다음 순서부터는 board 에서 moves 에 해당되는 원소 와 스택에 저장된 값을 비교한다.

바로 다음 중복되는 경우를 파악하기 위해 직전에 뽑은값과 현재 뽑은 원소를 비교하는것이다.

값을 비교했을때 같은 경우 스택을 비우고, answer를 2개 추가해준다.

4. 비교를 마친후 board의 원소를 0으로 저장한다.

=> 반복하여 검사할때 0인경우는 제외시키기때문에 다음행을 검사하기 위함이다.

 

<stack>

push = top에 원소를 추가

pop = top에 원소를 삭제

top = 스택의 가장 끝에 있는 원소를 반환