풀이
크레인 인형 뽑기를 할 때, 제일 위에 쌓여있는 인형부터 뽑아지므로 '스택' 자료구조를 이용하면 쉽게 해결할 수 있다.
문제에서 주어진 board를 각각의 stack에 넣는다. 주의할 점은 0일 때는 인형이 존재하지 않는 것이므로 0이 아닌 값만 스택에 push 해야 한다.
예를 들어 문제에 나온 예시를 기준으로 stack에 쌓이는 결과를 보면
| 3 | 4 | |||
| 5 | 2 | 2 | ||
| 1 | 4 | 5 | 1 | |
| 3 | 4 | |||
| 1 | 2 | 1 | 3 |
주어진 board를 stack에 넣고 나서 moves 배열을 하나씩 돌면서 인형 뽑기를 시작한다.
이때 moves 배열로 뽑힌 것을 담는 바구니 역시 stack으로 선언한다.
이제 문제에서 요구하는 상황을 위와 맞물려서 생각해보자.
1. 만약 같은 모양의 인형 두 개가 바구니에 연속해서 쌓이게 되면 두 인형은 터뜨려지면서 사라진다.
현재 바구니에 담긴 스택의 가장 상단 인형과 뽑기로 뽑은 인형이 같다면 터지면서 정답에 +2를 추가하면 된다.
2. 격자의 가장 아래 칸부터 차곡차곡 쌓여있다.
위에서 각 board의 입력을 stack에 쌓았다.
3. 만약 인형이 없다면 아무 일도 일어나지 않는다.
크레인으로 인형을 뽑았는데 만약에 빈 stack 이면 비교할 필요가 없다는 것이다. 인형이 없으니까.
#include <string>
#include <vector>
#include <stack>
#include <iostream>
using namespace std;
stack<int> st[31];
stack<int> ret;
int solution(vector<vector<int>> board, vector<int> moves) {
int answer = 0;
int len = board.size();
// 사전 작업
for(int i = len - 1; i >= 0; i--) {
for(int j = 0; j < len; j++) {
if(board[i][j] != 0)
st[j + 1].push(board[i][j]);
}
}
// 크레인 인형 뽑기 시작
for(int i = 0; i < moves.size(); i++) {
int idx = moves[i];
if(!st[idx].empty()) {
if(!ret.empty() && ret.top() == st[idx].top()) {
ret.pop();
answer += 2;
}
else {
ret.push(st[idx].top());
}
st[idx].pop();
}
}
return answer;
}'Algorithm' 카테고리의 다른 글
| [프로그래머스] 키패드 누르기 (C++) (0) | 2021.05.06 |
|---|---|
| [프로그래머스] 완주하지 못한 선수 (C++) (0) | 2021.04.30 |
| [백준 14469] 소가 길을 건너간 이유3 (C++) (0) | 2021.04.29 |
| [백준 2456] 나는 학급회장이다 (C++) (0) | 2021.04.28 |
| [백준 2696] 중앙값 구하기 (C++) (0) | 2021.04.22 |
