2019 크레인 인형뽑기
몇번 품?
- 21년 10월 06일
풀이전략
- 맨 처음에 이차원 벡터로 만들어서 board를 받으려고 했다.
- 근데 생각을 해보니, 인덱스 오름차순으로 진행하고,
- 맨 처음에 이차원 벡터로 만들어서 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;
}
#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;
}
완료!
Author And Source
이 문제에 관하여(2019 크레인 인형뽑기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kwt0124/2019-크레인-인형뽑기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)