프로그래머스 - 크레인 인형뽑기 게임

 

이제 코딩 테스트에 나올법한 긴 문제를 풀기 시작했습니다. 

하루에 알고리즘 한개를 풀되, 알고리즘 한개를 저의 단점을 파악하며 문제를 여러번 풀어 보는것을 목표로 삼았습니다. 

오늘은 카카오 개발자 채용 문제를 풀어 보았습니다 :) 

 

---

▶ 문제 설명 

[ 문제 ] 

게임개발자인 죠르디는 크레인 인형뽑기 기계를 모바일 게임으로 만들려고 합니다.
죠르디는 게임의 재미를 높이기 위해 화면 구성과 규칙을 다음과 같이 게임 로직에 반영하려고 합니다.

 

[ 제한 조건 ] 

• board 배열은 2차원 배열로 크기는 5 x 5 이상 30 x 30 이하입니다.
• board의 각 칸에는 0 이상 100 이하인 정수가 담겨있습니다.
  • 0은 빈 칸을 나타냅니다.
  • 1 ~ 100의 각 숫자는 각기 다른 인형의 모양을 의미하며 같은 숫자는 같은 모양의 인형을 나타냅니다.
• moves 배열의 크기는 1 이상 1,000 이하입니다.
• moves 배열 각 원소들의 값은 1 이상이며 board 배열의 가로 크기 이하인 자연수입니다.

---

▶ 첫 문제풀이 

처음에는 간단하게 짠다기 보다는 사용하기 편하도록 만들어 둔 후에 접근하려고 했던 것 같습니다. 

그래서 사용하기 편하도록 배열을 다시 vector<queue> copyList 로 변환하였고, 

그 후에 편하게 작업하는 방식으로 문제를 풀어나갔습니다.

 

#include <vector>
#include <stack>
#include <queue>

using namespace std;

int solution(vector<vector<int>> board, vector<int> moves) 
{
	stack<int> lineStack;
	vector<queue<int>> copyList;
	int answer = 0;
	copyList.resize(board[0].size());

	//1. row/col 변경
	for (int i = 0; i < board.size(); ++i)
	{
		for (int j = 0; j < board[i].size(); ++j)
		{
			if (board[i][j] != 0)
			{
				copyList[j].push(board[i][j]);
			}
		}
	}

	//2. move
	int moveNum = moves.size();
	int lineStackSize = 0;
	for (int i = 0; i < moveNum; ++i)
	{
		// 빈경우
		if (true == copyList[moves[i] - 1].empty())
		{
			continue;
		}
		// 터트려진 인형
		else if ((0 < lineStackSize) 
			&& (lineStack.top() == copyList[moves[i]-1].front()))
		{
			lineStack.pop();
			copyList[moves[i] - 1].pop();
			lineStackSize--;
			answer++;
		}
		// 쌓인 인형
		else
		{
			lineStack.push(copyList[moves[i]-1].front());
			copyList[moves[i] - 1].pop();
			lineStackSize++;
		}
	}

	// 터트린 갯수 * 2
	return (answer * 2);
}

 

 

처음에는 이렇게 난잡하게 코딩을 했습니다.;

정답은나왔지만, 딱봐도 코드가 너무 길고 쓸데없는 줄이 많죠 .. 

굳이 여러가지 자료구조를 써야할까도 싶습니다. 

생각의 흐름대로 짠 코드같은 느낌이 듭니다..

 

그래서 vector를 카피하지 않고 작성할 수 있는 간결한 코드를 다시 짜 보았습니다.

 

 

int solution(vector<vector<int>> board, vector<int> moves) 
{
	int answer = 0;
	int moveCount = moves.size();	// 움직인 개수
	int boardRow = board.size();	// 보드판 가로
	int boardCol = board[0].size(); // 보드판 세로. 정사각형이므로 0번째 기준

	stack<int> movedDollList;

	for (int i = 0; i < moveCount; ++i)
	{
		
		for (int j = 0; j < boardCol; ++j)
		{
			int doll = board[j][moves[i]-1];

			// 내려가다가 인형이 있다면 
			if (0 != doll)
			{
				// 인형이 터지는경우 
				if ((false == movedDollList.empty()) && (movedDollList.top() == doll))
				{
					movedDollList.pop();
					answer += 2;
				}
				else
				{
					movedDollList.push(doll);
				}
				board[j][moves[i] - 1] = 0;
				break;
			}
		}

	}
	return answer;
}

 

라인이 훨씬 짧아졌고, stack 한개만 사용하여 이동된 인형의 리스트들을 한번에 관리하니 보기도 수월해졌습니다.

이전 결과와 한번 비교해 볼게요.

 

 

왼쪽이 이전 결과, 오른쪽이 새로 짠 결과입니다.

Copy해서 재정렬하는 시간이 없으니 아무래도 오른쪽이 평균 0.01ms정도 감소한 것을 확인할 수 있습니다. 

 

간결하면서도 빠른 코드를 짜는 연습이 많이 필요할 것 같네요.

앞으로도 점점더 발전하는 알고리즘 올리도록 하겠습니다 :)