🤔 문제
🔗
게임 화면의 격자의 상태가 담긴 2차원 배열 board와 인형을 집기 위해 크레인을 작동시킨 위치가 담긴 배열 moves가 매개변수로 주어질 때, 크레인을 모두 작동시킨 후 터트려져 사라진 인형의 개수를 return 하도록 solution 함수를 완성해주세요.
🔑 풀이과정
N*N 크기의 정사각 격자에 인형이 들어있는 인형뽑기 게임이 있다. 사용자는 크레인을 통해 각 라인의 맨 위에 있는 인형을 뽑을 수 있으며, 뽑은 인형은 바구니로 들어간다. 바구니에 같은 인형이 연속으로 쌓이면 두 인형은 터지면서 바구니에서 사라진다.
이 게임에서 격자에 들어있는 인형의 상태가 담긴 2차원 배열 board와 크레인을 움직인 위치가 담긴 배열 moves가 매개변수로 주어질 때, 게임이 끝난 후 사라진 인형의 개수를 리턴하는 프로그램을 작성한다.
Stack
인형은 바구니에 차곡차곡 쌓이기 때문에 Stack을 사용해야 한다.
일단 뽑힌 인형의 중복여부를 확인하지 않은 채 모두 담아놓고 마지막에 인접한 인형들과 비교하여 제거할 수도 있었지만, 이왕 스택을 사용하는 김에 즉각적으로 확인하고 제거하는 방법을 사용하였다.
그렇다면 기존에 인형이 담겨있는 정사각 격자는 어떻게 해야할까?
방법은 두가지가 있다.
1) board 배열을 그대로 사용
이 경우 다음과 같이 이중 for문을 사용해야 한다.
for(int move : moves) {
for(int i=0;i<board.length;j++) {
if(board[i][move-1]!=0){
basket.push(board[j][move-1]);
board[i][move-1]=0;
break;
}
}
}move 변수를 통해 board의 인덱스가 [i][move-1]로 정해지면 for문을 통해 0이 아닌, 즉 인형이 있는 인덱스가 나올때까지 검색한다.
이 코드는 인형이 들어있는 인덱스가 나올 때까지 탐색을 계속해야 한다.
운이 좋으면 [0][move-1]에서 탐색이 종료될수도 있지만 최악의 경우 맨 밑까지 탐색한 후에야 해당 라인이 비어있음을 알게 될 수도 있다.
board 배열의 크기가 그렇게 크지 않아서 최악의 경우에도 성능에는 별 문제가 없을 것 같긴 하다.
2) Stack으로 재구성
크레인의 좌표인 라인을 기준으로 N개의 스택 배열 dolls를 만들고, board 배열을 담는다.
인형이 담기지 않은, 즉 값이 0인 인덱스는 스택에 담지 않는다.
Stack<Integer> dolls=new Stack[board.length];
for(int i=0 ; i<dolls.length ; i++) {
dolls[i]=new Stack<>();
for(int j=dolls.length-1 ; j>=0 ; j--) {
if(board[j][i]!=0) {
dolls[i].push(board[j][i]);
}
}
}기존의 board는 가로열을 기준으로 구성된 2차원 배열이라 세로축을 기준으로 라인이 정해져 있는 게임의 크레인과 직관적으로 매치가 되지 않았다.
그러나 위와 같이 board를 스택 dolls에 넣을 경우, 크레인 라인과 동일하게 세로축을 기준으로 재구성되기 때문에 직관적이다.
예를 들어 move의 값이 5, 즉 5번째 라인에서 인형을 뽑아야 한다면 dolls[5-1]에서 뽑아내면 된다.
또한 공백 없이 순수하게 인형만이 스택에 담기기 때문에 for문을 돌려 탐색해줄 필요 없이 pop()을 사용하면 된다.
for(int move : moves) {
if(!dolls[move-1].empty()) {
int pickedDoll=dolls[move-1].pop();
if(!basket.empty()) {
if(basket.peek()==pickedDoll) {
basket.pop();
answer+=2;
continue;
}
}
basket.push(pickedDoll);
}
}인형을 뽑고 뽑아낸 인형을 pickedDoll 변수에 저장한다.
pickedDoll을 basket에 들어있는 인형과 비교해 두 인형이 동일할 경우 제거하고, 다를 경우 basket에 담는다.
여기서 EmptyStackException을 주의해야 한다.
empty()를 사용해 스택이 비어있지 않을 경우에만 peek(), pop()하도록 해야 한다.
✨ 소스코드
import java.util.Stack;
public class 프로그래머스_2019카카오개발자겨울인턴십_크레인인형뽑기게임 {
public static int solution(int[][] board, int[] moves) {
int answer=0;
Stack<Integer> basket=new Stack<>();
Stack<Integer>[] dolls=new Stack[board.length];
for(int i=0 ; i<dolls.length ; i++) {
dolls[i]=new Stack<>();
for(int j=dolls.length-1 ; j>=0 ; j--) {
if(board[j][i]!=0) {
dolls[i].push(board[j][i]);
}
}
}
for(int move : moves) {
if(!dolls[move-1].empty()) {
int pickedDoll=dolls[move-1].pop();
if(!basket.empty()) {
if(basket.peek()==pickedDoll) {
basket.pop();
answer+=2;
continue;
}
}
basket.push(pickedDoll);
}
}
return answer;
}
}