[C++/알고리즘] 프로그래머스 (크레인 인형 뽑기)

 

programmers.co.kr/learn/courses/30/lessons/64061

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

 

 

 

stack을 사용해서 푸는 문제이다.

 

우선 인형뽑기 기계의 움직임. moves로 들어오는 정보들은 열을 기준으로 움직인다.

 

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

 

{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}

입력되는 값은 0번째 행, 1번째 행, 2번째 행, 3번째 행... 순으로 가로로 채워지게 된다.

 

그러므로 moves의 값이 1이라면 0번째의 열에 있는 0,0,0,4,3의 값 중 가장 위에 있는 4를 뽑아야 하며

moves의 값이 5라면 4번째 열에 있는 0,3,1,2,1의 값 중 3을 뽑아야 한다.

 

그렇게 뽑은 값은 stack을 이용한 basket에 넣어준다. 

basket에 정보를 넣어줄 때마다 바로 위에 있는 인형의 종류와 비교해 주었다.

문제의 조건은 터트린 인형의 '개수'를 구하는 것이므로 한 번 터트릴 때마다 두 개 씩 더해준다. 

인형의 종류가 같지 않다면 basket에 넣어준다. 

 

 

 

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

	stack<int> basket; 
	int cnt = moves.size();
	int board_width = board[0].size();

	for (int i = 0; i < cnt; ++i)
	{
		for (int j = 0; j < board_width; ++j)
		{
			if (board[j][moves[i] - 1] != 0)
			{
				int value = board[j][moves[i] - 1];

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

				else {
					basket.push(value);

				}

				board[j][moves[i] - 1] = 0;
				break;
			}
		}
	}
	return answer;
}

 

 

 

tech.kakao.com/2020/04/01/2019-internship-test/

 

2019 카카오 개발자 겨울 인턴십 코딩 테스트 문제 해설

문제 공식 해설! 

 

처음에 그냥 stack을 굳이 안써도 되겠지 하는 생각에 basket을 vector로 해서 풀었다. end() - 2의 방식으로 pop_back을 해줬더니 실행은 제대로 됐는데 제출을 하니 27점을 맞아 정신차리고 다시 stack으로 바꿔서 풀었다. 확실히 stack으로 푸니 코드 줄도 줄어들고 더 편하고, 정답이었다. 앞으로는 조건대로 제대로 풀어야겠다.. 

제일 많은 사람들이 푼 문제라 풀어봤는데 다음 문제 풀기가 두렵다 ^-^..