2019 크레인 인형뽑기

몇번 품?

  • 21년 10월 06일

풀이전략

  • 맨 처음에 이차원 벡터로 만들어서 board를 받으려고 했다.
  • 근데 생각을 해보니, 인덱스 오름차순으로 진행하고,

1번을 보면 초록 친구 위에 어피치가 있다.
2번을 보면 위에
있다.
근데 board와 비교하면

0번 인덱스의 꾸러미 다 들어오고,
1번 인덱스의 꾸러미 다 들어오고,
2번 인덱스의 꾸러미 다 들어오고,
3번 인덱스의 꾸러미 다 들어오고,
4번 인덱스의 꾸러미 다 들어오고,
순차적으로 들어온다.
이렇게 들어오니까,,, 이부분을 굉장히 생각을 많이 해야 한다.

해결책

  • 큐를 만들어서 먼저 들어오는 인덱스를 집어넣고 나중에 들어오는 값을
    추후에 넣어주면 멋들어지게 컨테이너를 만들 수 있을 것 같다고 생각했고,

  • 그래서 큐를 배열 형태로 만들어서 진행햇다.

문제점.


: front를 뽑아내기 전에 예외처리를 해야한다.
-> 문제에서 이러한 문장이 눈에 띄었다. 이거를 참고해서 코드를 작성해야 한다.

소스코드

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

//같은 모양의 인형이 쌓이면 두 인형은 바구니에서 사라진다.
//인형이 없는 번호를 집어도 아무런 일이 안일어난다.
//바구니는 모든 인형 들어갈만큼 크다.

//  0번인덱스  0 0 0 0 0 
//  1번인덱스  0 0 1 0 3
//  2번인덱스  0 2 5 0 1
//  3번인덱스  4 2 4 4 2
//  4번인덱스  3 5 1 3 1

//move : 1,5,3,5,1,2,1,4
//move의 마지막까지 진행했을때 사라진 인형의 갯수는?

int solution(vector<vector<int>> board, vector<int> moves) {
    int answer = 0;
    
    int size = board.size();
    queue<int>q[size];
    
    for(int i = 0; i < board.size(); i++)
    {
        for(int j = 0; j < board[0].size(); j++)
        {
            if(board[i][j] != 0)
                q[j].push(board[i][j]);
        }
    }
    
    //  0번인덱스  0 0 0 0 0 
    //  1번인덱스  0 0 1 0 3
    //  2번인덱스  0 2 5 0 1
    //  3번인덱스  4 2 4 4 2
    //  4번인덱스  3 5 1 3 1
    
    stack<int>st;
    //move의 마지막까지 진행했을때 사라진 인형의 갯수는?
    for(int i = 0; i < moves.size(); i++)
    {
        //동일한 인형 두개가 맞닿으면 같이 사라지고 이때 cnt+= 2;
        int num = moves[i] - 1;
        
        if(q[num].empty())
            continue;
        int data = q[num].front();
        q[num].pop();
        
        if(!st.empty())
        {
            if(st.top() == data)
            {
                answer += 2;
                st.pop();
            }
            else
            {
                st.push(data);
            }
        }
        else
        {
            st.push(data);
        }
        
       
    }

    
    return answer;
}


완료!

좋은 웹페이지 즐겨찾기