크레인 인형뽑기 게임

<풀기 전 생각>

뽑은 인형의 갯수가 불확실 하므로 길이가 가변적인 자료구조 사용이 필요하다 -> ArrayList, Set, Stack, Queue, Deck

나머지는 단순 for, if 문으로 해결이 가능해 보였다.

 

<중간 문제점>

처음에 1번 하고 2번이 런타임 에러가 나왔었는데  생각해보니 그 이유는 인형 뽑기에서 0을 뽑은 경우는 아무 것도 안한 걸로 취급해야 하는데 0을 뽑아서 담은 걸로 취급하는 식으로 코드를 짜서 해당 문제가 발생한 것 이었다.

 

<최종 코드>

import java.util.ArrayList;

class Solution {
    private int pickUp(int [][]board, int num){
        int doll=0;
        for(int i=0;i<board.length;i++){
            if(board[i][num-1]!=0){
                doll = board[i][num-1];
                board[i][num-1] = 0;
                break;
            }
        }
        return doll;
    }
    // 시간 복잡도 O(n*m) 공간 복잡도 O(n)
    public int solution(int[][] board, int[] moves) {
        int answer = 0;
        ArrayList<Integer> collections = new ArrayList<Integer>();
        // length-1 = -1 방지
        collections.add(0);
        for(int i=0;i<moves.length;i++){
            int lastIndex = collections.size()-1;
            int before = collections.get(lastIndex);
            int curr = pickUp(board,moves[i]);
            if(curr == 0)
                continue;
            if(before==curr) {
                collections.remove(lastIndex);
                answer+=2;
            }
            else
                collections.add(curr);
        }

        return answer;
    }
}

<메모>

가변적인 길이의 자료구조만을 생각해서 ArrayList를 사용하였는데 다시 생각해보니 Stack을 사용하는게 이 문제 취지에 훨씬 알맞는 내용이지 않았을까 싶다.