Programmers 코딩테스트 연습 64061 크레인 인형뽑기 게임
게임 화면의 격자의 상태가 담긴 2차원 배열 board와 인형을 집기 위해 크레인을 작동시킨 위치가 담긴 배열 moves가 매개변수로 주어질 때, 크레인을 모두 작동시킨 후 터트려져 사라진 인형의 개수를 return 하도록 solution 함수를 완성해주세요.
board 배열은 2차원 배열로 크기는 이상 이하입니다.
5 x 5
30 x 30
board의 각 칸에는 0 이상 100 이하인 정수가 담겨있습니다.
moves 배열의 크기는 1 이상 1,000 이하입니다.
moves 배열 각 원소들의 값은 1 이상이며 board 배열의 가로 크기 이하인 자연수입니다.
머리 속으로 암산하듯 설계하지 말고 어떻게 풀 지 종이에 먼저 써보자. 글로만 보면 visualizing에 소질이 없는 나는 코드짜기가 어려워지므로 배열을 보드형식으로 그렸고 for loop을 어떻게 돌릴 지, 배열 안에 어떤 수가 들어와야 맞는 지 생각했다. 항상 그렇듯 어느정도 생각한 대로 나왔지만 답은 틀렸다. 처음엔 크레인이 가져온 인형을 담는 바구니로 어레이리스트를 썼다. 그 과정에서 바구니는 밑에서부터 쌓이는 걸 감안해 보드에 있는 인형을 바구니의 사이즈를 moves와 같에 하고 [바구니.length - i]로 뒤에서부터 저장했고 그 결과 인형을 가져오지 않는 move 턴에는 바구니에 0이 쌓이게 되었다(..ㅠ). 그래서 어차피 같은 인형 두개가 들어오는 때에만 answer += 2를 해주면 되니 사이즈를 처음부터 정해주지 않고 바구니에 마지막으로 들어온 값과 크레인이 가져온 인형이 같은 지 확인하는데 이것도 인형이 없어지면 또 그 다음 값이 같은 지 봐야해서 어레이의 인덱스 값을 알아야 하는데 그 부분이 굉장히 헷갈렸다. for loop을 돌려야 할 지 뭘 해야할 지 모르겠어서.. 결국 검색했다. Stack 클래스로 해결한 풀이를 봤는데 새로 보는 클래스라 노트를 좀 적어뒀고 이런 문제를 풀 때 유용하겠다 싶었다. 말 그대로 stack이라 데이터가 밑에서부터 쌓이고 peek, pop 등의 함수를 쓰면 제일 위에 쌓인 엘리먼트를 가져온다. 풀이를 보고 생각해보니 어레이리스트로도 충분히 풀 수 있는 문제였고 두 방법을 이용해 풀었다.
import java.util.ArrayList;
import java.util.Stack;
class Solution {
public int solution(int[][] board, int[] moves) {
/*Stack<Integer> temp = new Stack<>();
temp.push(0);
int ani;
int answer = 0;
for (int i = 0; i < moves.length; i++) {
for (int j = 0; j < board.length; j++) {
ani = board[j][moves[i] - 1];
if (ani != 0) {
if (ani == temp.peek()) {
temp.pop();
answer += 2;
}else {
temp.push(ani);
}
board[j][moves[i] - 1] = 0;
break;
}
}
} // 여기까지가 Stack 이용해 풀이.
*/
ArrayList<Integer> temp = new ArrayList<>();
temp.add(0);
int answer = 0;
int animal;
for (int i = 0; i < moves.length; i++){
for (int j = 0; j < board.length; j++) {
animal = board[j][moves[i] - 1];
if (animal != 0) {
if (animal == temp.get(0)) {
answer += 2;
temp.remove(0);
} else {
temp.add(0, animal);
}
board[j][moves[i] - 1] = 0;
break;
}
}
}
return answer;
}