[Programmers] 2019 카카오 인턴십 1번 - 크레인 인형 뽑기 게임

[문제 설명]

각 열의 상단에 위치한 인형을 바구니로 옮긴다.

옮겨진 인형이, 바구니의 맨 위에 놓인 인형과 같은 경우 사라진다.

총 사라지는 인형의 개수를 구하는 문제.

 

[조건]

1 <= len (board[][]) <= 30

1 <= 인형 종류 <= 100

 

[풀이]

간단한 시뮬레이션 문제이다.

다만 입력으로 주어지는 board가 실제 인형의 배치가 다르다는 점만 유의하면 된다.

(ex. board[0][0] -> 0열의 가장 상단을 의미 / board[0][len - 1] -> 0 열의 가장 하단을 의미)

 

자료 구조로는 stack을 이용하였다.

Queue를 사용하여 구현하여도 상관 없다.

그러나, 각 열을 탐색하였을 때, 0이 나오면 다음 열로 넘어가는 것이 효율적인 풀이인데.

 

그렇기 위해서는 바닥부터 탐색을 해야한다.

Queue를 사용하면, 바닥에 있는 인형이 가장 먼저 나오게 되므로. 그래서 stack을 사용하였다.

 

import java.util.Stack;

public class Programmers_kakao2019_intern_1 {
	public static int solution(int[][] board, int[] moves) {
		int answer = 0;
		Stack<Integer> basket = new Stack<Integer>();
		Stack<Integer> st[] = new Stack[board.length + 1]; // 각 열의 인형 상태 저장
		
		
		for (int c = 1; c <= board.length; ++c) {          // 열부터 탐색
			st[c] = new Stack<>();
			
			for (int r = board.length - 1; r >= 0; --r) {  // 인덱스 주의 
				if (board[r][c - 1] == 0)                  // 비어 있는 경우 다음 열 탐색
					break;
				
				st[c].push(board[r][c - 1]);
			}
		}
		
		for (int m = 0; m < moves.length; ++m) {
			int curCol = moves[m];
			
			if (!st[curCol].isEmpty()) {                      // 채워져 있으면 진행
				
				if (!basket.isEmpty()) {                      // 비교할 대상이 있으면
					if (basket.peek() == st[curCol].peek()) { // 터뜨릴 수 있는 경우
						answer += 2;
						basket.pop();
						st[moves[m]].pop();
					}
					else {                                    // 인형이 다른 경우
						basket.add(st[curCol].pop());
					}
				}
				
				else {                                        // basket에 그냥 담기
					basket.add(st[curCol].pop());
				}
			}
		}
		return answer;
	}
	
	public static void main(String[] args) {
		System.out.println(solution(new int[][] {{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}}, new int[] {1,5,3,5,1,2,1,4}));
	}
}

 

 

https://programmers.co.kr/learn/courses/30/lessons/64061

코딩테스트 연습 - 크레인 인형뽑기 게임