64061. 크레인 인형뽑기 게임

시간 복잡도: O(NM), N = number of moves, M = width of the Board

1#include <bits/stdc++.h>
2using namespace std;
3
4int solution(vector<vector<int>> board, vector<int> moves) {
5  int answer = 0;
6  const int D = board.size();
7  stack<int> stk;
8
9  for(int j : moves) {
10    for(int i=0; i<D; ++i) {
11      if(board[i][j-1] > 0) {
12        if(stk.size()) {
13          int temp = stk.top();
14          if(temp == board[i][j-1]) {
15            while(temp == board[i][j-1]) {
16              ++answer;
17              stk.pop();
18              if(!stk.empty()) temp = stk.top();
19              else break;
20            }
21          } else {
22            stk.push(board[i][j-1]);
23          }
24        } else {
25          stk.push(board[i][j-1]);
26        }
27        board[i][j-1] = 0;
28        break;
29      }            
30    }    
31  }
32
33  return answer*2;
34}

인형들을 스택에 하나씩 쌓으면서 동일한 인형이 있는지 확인. 연속으로 1 - 2 - 2 - 1 이런식으로 될 수 있지 않을까 해서 중간에 while문을 사용했는데, 지금 생각해보면 바로바로 제거해주니까 굳이 필요는 없었다는 걸 느끼고 있다.

실제로 아래처럼 while문만 지우고 제출했더니 AC받았다.

1if(temp == board[i][j-1]) {
2  ++answer;
3  stk.pop();
4}