[프로그래머스] 인형뽑기

소스 보러가기
문제 보러가기

---

사용한 알고리즘 및 자료구조
Sol 1 : ArrayList, Sol 2 : Stack

풀이
따로 알고리즘 구현이 필요 없는 문제이다. ArrayList, List, Stack 과 같은 자료구조 개념을 알고 있다면 쉽게 풀 수 있는 문제이다.

1. 열 순서대로 인형 탐색

2. 인형 있으면 -> 해당 칸 빈칸으로

3. Stack or List 마지막 칸과 비교 같으면 삭제 후 정답 카운트 증가
   다르면 맨 뒤에 추가

4. moves배열의 길이만큼 수행했다면 정답 카운트 출력

상당히 간단하다. Stack, List 둘다 가능할 것이라 생각하여 solution을 2개 만들었다.

로직은 같고 차이점은 Stack은 뽑는 행위가 디폴트 값으로 마지막 위치에 인형을 뽑는다. 그리고List는 (인덱스 값-1)을 매개변수로 get()을 이용하여 바구니 마지막 위치에 있는 인형을 출력한다.

// before test, have to delete 'static' keywords
    public static int solution(int[][] board, int[] moves) {
        int answer = 0;
 
        ArrayList<Integer> box = new ArrayList<Integer>();
 
        for (int idx = 0; idx < moves.length; idx++) {
 
            int row = moves[idx] - 1;
 
            for (int col = 0; col < board.length; col++) {
 
                int boxLastIdx = box.size() - 1;
 
                if (board[col][row] != 0) {
 
                    if (box.isEmpty()) {
                        box.add(board[col][row]);
                    } else {
 
                        if (box.get(boxLastIdx) == board[col][row]) {
 
                            box.remove(boxLastIdx);
                            answer += 2;
                        } else {
                            box.add(board[col][row]);
                        }
 
                    }
                    board[col][row] = 0;
 
                    break;
 
                }
 
            }
 
        }
 
        return answer;
    }
    
 
    public int solution2(int[][] board, int[] moves) {
        Stack<Integer> box = new Stack<Integer>();
 
        int answer = 0;
        for (int i = 0; i < moves.length; i++) {
            int row = moves[i];
            for (int col = 0; col < board.length; col++) {
                if (board[col][row - 1] != 0) {
 
                    if (box.empty()) {
                        box.push(board[col][row-1]);
                    } else {
 
                        if (box.peek() == board[col][row-1]) {
                            box.pop();
                            answer += 2;
                        } else {
 
                            box.push(board[col][row-1]);
                        }
 
                    }
                    board[col][row-1] = 0;
 
                    break;
                }
 
            }
 
        }
 
        return answer;
    }