[프로그래머스 / C++] 크레인 인형뽑기 게임
5612 단어 psprogrammersprogrammers
https://programmers.co.kr/learn/courses/30/lessons/64061
1. 배열을 그대로 사용하는 법
#include <vector>
#include <stack>
#include <iostream>
using namespace std;
int solution(vector<vector<int>> board, vector<int> moves) {
int answer = 0;
stack<int> bucket;
for (auto move: moves) {
int col = move - 1; //0행부터 시작하므로
int row = 0; //가장 윗줄부터 확인
while (row < board.size()) {
// 빈 칸이라면
if (!board[row][col]) {
row++; //다음 줄
continue;
}
// 빈 칸이 아니라면
int doll_num = board[row][col];
board[row][col] = 0; //뽑아서 0으로
if (bucket.empty()) { //1. 스택이 비어있음
bucket.push(doll_num); //바로 삽입.
break;
}
if (bucket.top() == doll_num) { //2. 같은 모양 2개가 연속해서 들어있음
bucket.pop();
answer += 2;
} else bucket.push(doll_num); //3. 같은 모양이 아님
break;
}
}
return answer;
}
int main() {
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};
cout << solution(board, moves);
}
각 열을 스택으로 전처리
stack map[board.size()];
#include <vector>
#include <stack>
#include <iostream>
using namespace std;
int solution(vector<vector<int>> board, vector<int> moves) {
int answer = 0;
stack<int> bucket;
stack<int> map[board.size()];
//각 열마다 stack 전처리
for (int j = 0; j < board.size(); j++) { //열
for (int i = board.size() - 1; i >= 0; i--) {//행 : 맽 밑부터
if (board[i][j]) map[j].push(board[i][j]);
else break; //0이 나오면 바로 break;
}
}
for (auto move: moves) {
int col = move - 1; //0열부터 시작하므로
//해당 열의 스택 확인
if (!map[col].empty()) {
int doll_num = map[col].top(); //가장 위에 있는 인형
map[col].pop(); //뽑기
if (bucket.empty()) { //버킷이 비어있으면 바로 push
bucket.push(doll_num);
continue;
}
//버킷이 비어있지 않을 때 버킷의 top과 현재 뽑은 인형 비교
if (bucket.top() == doll_num) {
bucket.pop();
answer += 2;
} else {
bucket.push(doll_num);
}
}
}
return answer;
}
int main() {
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};
cout << solution(board, moves);
}
Author And Source
이 문제에 관하여([프로그래머스 / C++] 크레인 인형뽑기 게임), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@inryu/프로그래머스-C-크레인-인형뽑기-게임저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)