[Java] 프로그래머스 > 크레인 인형뽑기 게임
https://programmers.co.kr/learn/courses/30/lessons/64061
문제 설명
- 게임개발자인 "죠르디"는 크레인 인형뽑기 기계를 모바일 게임으로 만들려고 합니다.
"죠르디"는 게임의 재미를 높이기 위해 화면 구성과 규칙을 다음과 같이 게임 로직에 반영하려고 합니다.
- 게임 화면은 "1 x 1" 크기의 칸들로 이루어진 "N x N" 크기의 정사각 격자이며 위쪽에는 크레인이 있고 오른쪽에는 바구니가 있습니다. (위 그림은 "5 x 5" 크기의 예시입니다).
- 각 격자 칸에는 다양한 인형이 들어 있으며 인형이 없는 칸은 빈칸입니다.
- 모든 인형은 "1 x 1" 크기의 격자 한 칸을 차지하며 격자의 가장 아래 칸부터 차곡차곡 쌓여 있습니다.
- 게임 사용자는 크레인을 좌우로 움직여서 멈춘 위치에서 가장 위에 있는 인형을 집어 올릴 수 있습니다. 집어 올린 인형은 바구니에 쌓이게 되는 데, 이때 바구니의 가장 아래 칸부터 인형이 순서대로 쌓이게 됩니다. 다음 그림은 [1번, 5번, 3번] 위치에서 순서대로 인형을 집어 올려 바구니에 담은 모습입니다.
- 만약 같은 모양의 인형 두 개가 바구니에 연속해서 쌓이게 되면 두 인형은 터뜨려지면서 바구니에서 사라지게 됩니다. 위 상태에서 이어서 [5번] 위치에서 인형을 집어 바구니에 쌓으면 같은 모양 인형 두 개가 없어집니다.
- 크레인 작동 시 인형이 집어지지 않는 경우는 없으나 만약 인형이 없는 곳에서 크레인을 작동시키는 경우에는 아무런 일도 일어나지 않습니다. 또한 바구니는 모든 인형이 들어갈 수 있을 만큼 충분히 크다고 가정합니다. (그림에서는 화면표시 제약으로 5칸만으로 표현하였음)
- 게임 화면의 격자의 상태가 담긴 2차원 배열 board와 인형을 집기 위해 크레인을 작동시킨 위치가 담긴 배열 moves가 매개변수로 주어질 때, 크레인을 모두 작동시킨 후 터트려져 사라진 인형의 개수를 return 하도록 solution 함수를 완성해주세요.
제한 사항
- board 배열은 2차원 배열로 크기는 "5 x 5" 이상 "30 x 30" 이하입니다.
- board의 각 칸에는 0 이상 100 이하인 정수가 담겨있습니다.
- 0은 빈 칸을 나타냅니다.
- 1 ~ 100의 각 숫자는 각기 다른 인형의 모양을 의미하며 같은 숫자는 같은 모양의 인형을 나타냅니다.
- moves 배열의 크기는 1 이상 1,000 이하입니다.
- moves 배열 각 원소들의 값은 1 이상이며 board 배열의 가로 크기 이하인 자연수입니다.
스택을 이용하여 풀 수 있는 문제이다.
스택 자료구조에 대한 간단한 메서드는 다음과 같다.
Stack
- push(E item) : item을 Stack의 top에 삽입
- pop() : top에 있는 item을 삭제하고 item을 반환
- peek() : top에 있는 item을 삭제하지 않고 item을 반환
- empty() : Stack이 비어있으면 true를 그렇지 않으면 false 반환
- search(Object o) :해당 Object의 위치를 반환
풀이 방법
1. 바구니 역할인 stack을 선언한 뒤 0을 넣어준다 -> 처음 값과 비교할 대상이 필요하므로 0을 넣어줌
2. moves 길이와 board 길이만큼 이중 반복문을 통해 board [j][moves [i]-1]을 검사한다.
- board [j][moves [i]-1]이 0이 아닌 경우,
stack의 top 요소와 board [j][moves [i]-1] 값이 같다면 stack에서 pop을 하여 요소를 반환하고 answer값에 2를 더한다.
stack의 top 요소와 board [j][moves [i]-1] 값이 다르다면 stack에서 해당 값을 push을 한다.
또한 인형을 뽑았으므로 해당 자리의 값은 0으로 바꿔준다. -> board[j][moves[i] - 1] = 0;
- board[j][moves[i]-1]이 0인 경우, 인형이 없기 때문에 pass한다.
코드
import java.util.*;
class Solution {
public int solution(int[][] board, int[] moves) {
int answer = 0;
int result[]= new int[moves.length];
Stack<Integer> stack = new Stack<>();
stack.push(0);
for(int i=0;i<moves.length;i++){
for(int j=0;j<board[0].length;j++){
if(board[j][moves[i]-1]!=0){
if (stack.peek() == board[j][moves[i] - 1]) {
stack.pop();
answer += 2;
}else{
stack.push(board[j][moves[i] - 1]);
}
board[j][moves[i] - 1] = 0;
break;
}
}
}
return answer;
}
}
stack 자료구조가 생각나지 않아 arrayList로 접근했다.
풀이 방법
1. 바구니 역할인 result 리스트를 선언한다.
2. board [j][moves [i]-1]이 0이 아닐 경우 즉, 인형이 존재할 경우 result에 해당 값을 추가하고 board [j][moves [i]-1]을 0으로 수정한다.
3. 반복문을 통해 result 리스트를 검사한다.
- 인덱스 k가 리스트의 마지막 요소가 아닐 때, 해당 요소와 다음 요소의 값이 같다면 두 값을 제거하고 answer에 2를 더해준다.
- ArrayList에서 요소가 삭제되면 index가 한 칸씩 밀리기 때문에 result.remove(k); 을 두 번 반복하여 연속되는 숫자를 삭제해주고 k-1을 통해 리스트 길이도 수정한다.
다른 풀이
import java.util.ArrayList;
class Solution {
public int solution(int[][] board, int[] moves) {
int answer = 0;
ArrayList<Integer> result = new ArrayList<Integer>();
for(int i=0;i<moves.length;i++){
for(int j=0;j<board.length;j++){
if(board[j][moves[i]-1]!=0){
result.add(board[j][moves[i]-1]);
board[j][moves[i]-1]=0;
break;
}
}
}
for(int k=0;k<result.size();k++){
if(k!=(result.size()-1)){
if(result.get(k)==result.get(k+1)){
result.remove(k);
result.remove(k);
answer+=2;
k=-1;
}
}
}
return answer;
}
}