크레인 인형뽑기 게임

Posted on Edited on In , ,

문제정의

말그대로 인형뽑기 게임이다. 게임판은 2차원 배열(board)이 주어진다. 그리고 인형을 뽑는 순서로 1차원 배열(moves)이 주어진다. 뽑은 인형은 바구니에 쌓이고 만약 새로 뽑은 인형이 바구니의 가장 위에 있는 인형과 동일한 인형일 경우 인형은 터진다. 이때 터진 인형의 개수를 반환하면 된다.

문제풀이

이 문제를 해결하기 위해 가장 brute force적인 방법을 생각해보면 1. moves의 원소를 순회하면서 0이 아닌 지점까지 아래로 파고든다 2. 인형을 꺼낸 뒤, 해당 위치를 0으로 만든다. 3. 뽑은 인형은 스택에 저장한다. 만약 스택의 가장 위에 있는 인형과 똑같은 id를 공유한다면, 스택에서 pop한 뒤 answer에 2를 더해준다.

이 경우 시간복잡도는 \(O(n^2)\)이 된다.

같은 \(O(n^2)\)이긴 하지만, 필자는 시간을 더 줄이기 위해 top이란 1차원 배열을 추가로 생성한다. top의 원소는 각 열에서 인형이 놓여있는 가장 높은 위치를 말한다.

crane_game_101

이 경우의 top은 각각 [3,2,1,3,1]이다(맨 윗줄이 0번째).

이렇게 하면 앞서 말한 1번 과정에서 시간을 단축할 수 있다. 계속 아래로 파고드는 것이 아니라 해당 인덱스로 바로 접근하는 것이기 때문이다. 이제 코드와 함께 보도록 하자. 코드는 자바로 작성되었다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import java.util.*;

public class CrainDoll {
    public static void main(String[] args) {
        int[][] board = {
            {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}
        };
        int[] moves = {1,5,3,5,1,2,1,4};
        int answer = 0;
        int[] top = new int[board.length];
        Arrays.fill(top, 40);
        for(int c = 0; c < board.length; c++)
        {
            for(int r = 0; r < board.length; r++)
            {
                if(board[r][c] != 0)
                {
                    top[c] = r;
                    break;
                }
                    
            }
        }
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i < moves.length; i++)
        {
            if(top[moves[i]-1] < board.length)
            {
                int doll = board[top[moves[i]-1]][moves[i]-1];
                if(stack.empty())
                    stack.push(doll);
                else if(stack.peek() == doll)
                {
                    stack.pop();
                    answer += 2;
                }
                else
                    stack.push(doll);
                
                top[moves[i]-1]++;
            }
        }
        System.out.println(answer);
    }
  }

전체코드

1
2
3
4
5
6
7
int[][] board = {
    {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}
};
int[] moves = {1,5,3,5,1,2,1,4};
int answer = 0;
int[] top = new int[board.length];
Arrays.fill(top, 40);

문제 세팅을 위한 코드이다 board와 moves를 설정하고 터트려질 인형의 수를 answer라고 한다. 그리고 top의 길이는 board의 가로 또는 세로 사이즈로 설정한다. 이때 top을 0으로 초기화하면 안되는 이유는 유효한 값이기 때문이다. 문제에서 보드판은 30*30까지 될 수 있고 이말은, 0~29까지는 실제 인형이 있는 위치를 나타내는 숫자이다. 따라서 이 범위내에 있지 않은 숫자로 초기화한다.

1
2
3
4
5
6
7
8
9
10
11
12
for(int c = 0; c < board.length; c++)
{
    for(int r = 0; r < board.length; r++)
    {
        if(board[r][c] != 0)
        {
            top[c] = r;
            break;
        }
            
    }
}

top을 초기화하는 코드이다 board를 순회하는데 순회는 위에서 아래로 한줄씩 본다. 만약 처음으로 0이 아닌 숫자가 나오면 그 위치를 저장하고 다음 줄로 넘어간다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Stack<Integer> stack = new Stack<>();
for(int i = 0; i < moves.length; i++)
{
    if(top[moves[i]-1] < board.length)
    {
        int doll = board[top[moves[i]-1]][moves[i]-1];
        if(stack.empty())
            stack.push(doll);
        else if(stack.peek() == doll)
        {
            stack.pop();
            answer += 2;
        }
        else
            stack.push(doll);
        
        top[moves[i]-1]++;
    }
}
System.out.println(answer);

바구니를 나타낼 stack을 선언한다 밑에 있는 for문은 앞서말한 3번과정을 나타낸다. 뽑아야하는 열이 주어질 때 top이 유효범위 내에 있다면 인형의 id를 저장한다. 만약 바구니가 비어있다면 스택에 인형을 집어넣는다. 만약 바구니의 맨 위에 있는 인형과 뽑은 인형이 같다면(else if문) 스택에서 인형을 꺼내고, 답을 2증가한다. 맨 위에있는 인형과 뽑은 인형이 같지 않다면 바구니에 넣어준다. 인형을 뽑고나면 top의 해당원소를 1증가하여 인형이 뽑혔다는 것을 저장한다.

테스트

crane_game_result

코딩테스트를 너무 늦게 준비해서 조급한 마음도 있지만 1레벨부터 찬찬히 풀어가야겠다.