[자바] 프로그래머스 - 크레인 인형뽑기 게임 (Lv1, Java)

문제 : Programmers-크레인 인형뽑기 게임

문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

 

 

필요 알고리즘 개념

• 시뮬레이션
  
  • 문제에서 제시된 대로 구현만 해주면 된다.
• 스택
  
  • 배열 자체로 구해도 문제 없으나, 로직 구성상 스택을 활용하면 더 깔끔하게 구현 가능하다

 

 

  배열 자체에서 진행해도 되지만, 실수를 확실히 줄일 수 있고 더 맞는 자료구조가 있다면 그걸 쓰는게 맞다고 본다. 이 문제의 경우 각 열에 대해 스택 자료구조를 사용하고, 바구니도 스택을 사용할 시 코드 설계가 매우 깔끔해지고 실수의 여지도 많이 줄어든다. 그러니 스택을 사용해서 한번 구현해보자.

 

  예를들어 코드상의 stk[]과 basket은 다음과 같은 스택 구조를 나타낸다.

 

  구현 자체는 문제에서 제시된 대로만 구현하면 되므로, 별도로 알고리즘 풀이는 필요없다. 실수만 하지 않도록 구현해주면 된다.

 

  내 구현 로직은 코드에 주석으로 달아두었다.

 

 

코드 : github

/**
 * 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges
 */
import java.util.Stack;

class Solution {
    public int solution(int[][] board, int[] moves) {
        int r = board.length;
        int c = board[0].length;
        Stack<Integer>[] stk = new Stack[c];
        for (int j = 0; j < c; j++) {
            stk[j] = new Stack<>();
        }
        for (int j = 0; j < c; j++) {	// 각 열을 기준으로
            for (int i = r-1; i >= 0; i--) {	//각 행의 아래쪽부터 보면서
                if (board[i][j] == 0) break;	// 빈공간이 나올 때 까지
                stk[j].add(board[i][j]);	// 스택에 인형을 넣어준다.
            }
        }

        Stack<Integer> basket = new Stack<>();	// 바구니도 스택으로 표현한다.
        int cnt = 0;
        for (int cur : moves) {	// moves를 순회한다. 이 때 cur-1이 스택의 인덱스값이다.
            if (stk[cur-1].isEmpty()) continue;	// '만약 인형이 없는 곳에서 크레인을 작동시키는 경우에는 아무런 일도 일어나지 않습니다' 예외처리
            int doll = stk[cur-1].pop();	// doll : 현재 뽑힌 인형 번호
            if (!basket.isEmpty() && basket.peek() == doll) {	// 바구니의 가장 위(스택의 top)에 있는게 현재 doll과 동일하다면
                cnt++;	// 제거횟수를 증가시키고
                basket.pop();	// 바구니의 가장 위쪽을 빼준다.
            } else {	// 바구니의 가장 위에 있는게 doll과 다르다면
                basket.push(doll);	// 바구니에 넣어준다.
            }
        }
        return cnt*2;	// 한번 제거 시 2개씩 제거되므로 2를 곱한 값이 답이된다.
    }
}