2019 카카오 인턴쉽: 크레인 인형 뽑기 게임

[문제 링크]

코딩테스트 연습 - 크레인 인형뽑기 게임

---

스택을 사용하면 쉽게 풀 수 있는 문제였다.

 

배열 기준으로 move[i] - 1 위치에서 인형을 뽑게 되고, 인형을 찾을 때 까지(배열 원소가 0이 아닌 지점) depth = 0 부터 (board.size()-1) 까지 탐색한다.

 

인형을 찾으면 탐색을 종료하고 인형을 바구니에 담는다. 이때 바구니의 가장 위에 있는 인형과 동일한 인형이라면 가장 위에 있는 인형을 제거하고 answer 값을 2 증가시킨다.

 

만약 depth == board.size() 라면 인형을 못찾은 것이므로 건너뛰도록 구현하였다.

---

#include <string>
#include <stack>
#include <vector>

using namespace std;

int solution(vector<vector<int>> board, vector<int> moves) {
	int answer = 0;
	stack<int> basket;

	for (int i = 0; i < moves.size(); i++)
	{
		int depth = 0;

		while (depth < board.size() && board[depth][moves[i] - 1] == 0)
			depth++;

		if (depth == board.size())
			continue;

		int pick = board[depth][moves[i] - 1];
		
		board[depth][moves[i] - 1] = 0;

		if (!basket.empty() && basket.top() == pick)
		{
			basket.pop();
			answer += 2;
		}
		else
			basket.push(pick);

	}

	return answer;
}

알고리즘 200일 프로젝트 - 138 day