코딩테스트 : 크레인 인형뽑기 게임

문제 설명
해당 문제는 크레인을 이용해 인형을 집어올리고 바구니에 담는 게임에서 같은 인형이 연속으로 쌓이면 터뜨리는 방식으로, 최종적으로 터진 인형의 총 개수를 구하는 시뮬레이션 문제이다.

인형이 있는 첫 번째 칸을 찾고 바구니에 넣은 뒤, 같은 인형이 연속되면 제거하는 로직이 핵심이다.

 

핵심 풀이 방법

2차원 배열 board에서 moves에 따라 열을 지정하고, 그 열에서 위에서부터 인형을 찾는다.

찾은 인형은 바구니 역할을 하는 stack(여기서는 vector<int> result)에 넣는다.

바구니 안에 같은 인형이 연속되면 pop하여 두 개를 제거하고, 그때마다 정답에 +2씩 더한다.

 

int solution(vector<vector<int>> board, vector<int> moves) {
    int answer = 0;                    // 터진 인형 개수를 저장할 변수
    vector<int> result;               // 바구니 역할을 할 stack
    
    for(int pick : moves)             // 크레인을 작동시킬 위치 하나씩 순회
    {
        bool run = true;              // 인형을 찾을 때까지 반복할 플래그
        int i = 0;                    // 각 열에서 위에서부터 탐색
        
        while(run)
        {
            run = false;              // 일단 한 번만 실행하도록 설정
            
            if(board[i][pick-1] == 0) // 현재 칸에 인형이 없으면
            {
                i++;                  // 다음 행(더 아래 칸)으로 이동
                if(i == board.size())// 보드 끝까지 갔으면 멈춤
                    break;
                run = true;           // 아직 인형 못 찾았으니 다시 반복
            }
            else                      // 인형을 찾은 경우
            {
                result.push_back(board[i][pick-1]); // 바구니에 인형 넣기
                board[i][pick-1] = 0;               // 집은 인형은 제거(0 처리)
                
                // 바구니에 인형이 2개 이상 있고, 위에서 두 개가 같으면
                while(result.size() >= 2 && result[result.size() - 1] == result[result.size() - 2])
                {
                    result.pop_back();              // 위에 있는 인형 제거
                    result.pop_back();              // 아래에 있던 인형 제거
                    answer += 2;                    // 두 개 터졌으니 +2
                }
            }
        }
    }
    
    return answer;                    // 최종적으로 터진 인형 개수 반환
}