[코딩테스트합격자되기-자바편] 문제13. 크레인 인형뽑기 게임

💡 해당 풀이는 코딩 테스트 합격자되기 - 자바편 에서 발췌된 내용을 바탕으로 작성되었습니다.

 

문제

출처: 프로그래머스 - 크레인 인형 뽑기 게임

 

내용

 

게임개발자인 죠르디는 크레인 인형뽑기 기계를 모바일 게임으로 만들려고 합니다.
죠르디는 게임의 재미를 높이기 위해 화면 구성과 규칙을 다음과 같이 게임 로직에 반영하려고 합니다.

게임 화면은 1 x 1 크기의 격자로 이루어진 N x N 크기의 정사각 격자이며 위쪽에는 크레인이 있고 오른쪽에는 바구니가 있습니다.

각 격자 칸에는 다양한 인형이 들어 있으며 인형이 없는 칸은 빈칸입니다. 인형은 격자 한 칸을 차지하며 격자의 가장 아래 칸부터 차곡차곡 쌓입니다. 플레이어는 크레인을 좌우로 움직일 수 있고 크레인을 멈춘 위치에서 가장 위에 있는 인형을 집어 올릴 수 있습니다. 집어 올린 인형은 바구니에 쌓입니다, 이때 바구니의 가장 아래 칸부터 인형이 순서대로 쌓입니다.

이 상태에서 네모 인형이 1개 더 들어가면 어떻게 될까요?

같은 모양의 인형 두 개가 바구니에 연속해서 쌓이게 되면 두 인형은 펑하고 터지며 사라집니다. 만약 인형이 없는 곳에서 크레인을 작동시키면 아무 일도 일어나지 않습니다. 또 바구니는 모든 인형이 들어갈 수 있을 만큼 충분히 큽니다. 2차원 배열 board와 인형을 집는 크레인을 작동시킨 위치가 담긴 배열 moves가 주어질 때 크레인을 모두 작동시킨 후 사라진 인형 개수를 반환하는 solution()함수를 완성하세요.

 

제약 조건

• board 배열은 2차원 배열, 크기는 "5 x 5" 이상 "30 x 30" 이하입니다.
• board의 각 칸에는 0 이상 100 이하인 정수가 담겨있습니다.
  • 0은 빈 칸을 나타냅니다.
  • 1 ~ 100의 각 숫자는 각기 다른 인형의 모양을 의미하며 같은 숫자는 같은 모양의 인형을 나타냅니다.
• moves 배열의 크기는 1 이상 1,000 이하입니다.
• moves 배열 각 원소들의 값은 1 이상이며 board 배열의 가로 크기 이하인 자연수입니다.

 

기록하기

💡 어디까지 생각해봤는지 단계적으로 기록해봅니다.

어떤 알고리즘을 적용하려 했나요?

적용 근거는 무엇인가요?

바구니는 스택으로 적용한다.

문제 풀이 과정에서 해당 알고리즘을 어떻게 코드로 구현하려 했나요?

moves 에 따라 board의 x축을 움직여 해당 열에서 가장 상위 행(오름차순)에 있는 숫자를 변수에 담고 해당 위치는 0으로 바꾼다.

바구니는 pop 시킨 값들을 임시로 보관하는 스택과 바구니를 나타내는 stack으로 분리한다.

-> 들어올 때 모양이 같은 인형은 없어지기 때문에 임시 stack 만들지 않아도 된다.

크레인이 작동할 때마다 바구니 stack을 확인한다.

 

풀이

풀이 시간

 

시작 시각	종료 시각	총 소요 시간
17:50	18:50	60분

 

문제 분석

 

제약 사항 파악 & 테스트 케이스 작성

• board 배열은 2차원 배열, 크기는 "5 x 5" 이상 "30 x 30" 이하입니다.
• board의 각 칸에는 0 이상 100 이하인 정수가 담겨있습니다.
  • 0은 빈 칸을 나타냅니다.
  • 1 ~ 100의 각 숫자는 각기 다른 인형의 모양을 의미하며 같은 숫자는 같은 모양의 인형을 나타냅니다.
• moves 배열의 크기는 1 이상 1,000 이하입니다.
• moves 배열 각 원소들의 값은 1 이상이며 board 배열의 가로 크기 이하인 자연수입니다.

 

입력값 분석

💡 입력값을 분석하면 문제에서 요구하는 알고리즘의 시간 복잡도를 간접적으로 파악할 수 있습니다.

board	moves	result
[[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]]	[1,5,3,5,1,2,1,4]	4

 

 

의사 코드 작성

💡 의사 코드는 동작 중심으로 작성하는 것이 중요합니다.

💡 의사 코드는 문제 해결 순서로 작성합니다.

💡 의사 코드를 충분히 테스트해봅니다.

solution(board, moves) {
    Stack<Integer> 바구니 = new Stack<>();
    for (move : moves) {
        doll = 0;
        // 인형 위치 탐색
        for (j=move-1, i=0; board) {
            // 크레인으로 인형 가져오기
            if (board[i][j] != 0) {
                doll = board[i][j];
                board[i][j] = 0;
                break;
            }
        }

        // 인형 확인
        if (doll == 0) {
            continue;
        }

        // 인형 넣으면서 바구니 확인하기
        if (바구니.isEmpty()) {
            바구니.push(doll);
        } else {
            // 인형이랑 바구니 top 비교
            if (doll == 바구니.peek) {
                바구니.pop();
                answer += 2;
            } else {
                바구니.push(doll);
            }
        }
    }
    return answer;
}

 

 

구현

import java.util.Stack;

class Solution {
    public int solution(int[][] board, int[] moves) {
        Stack<Integer> 바구니 = new Stack<>();
        int answer = 0;
        for (int move : moves) {
            int doll = 0;
            // 인형 위치 탐색
            for (int i=0, j=move-1;i < board.length; i++) {
                // 크레인으로 인형 가져오기
                if (board[i][j] != 0) {
                    doll = board[i][j];
                    board[i][j] = 0;
                    break;
                }
            }

            if (doll == 0) {
                continue;
            }

            // 인형 넣으면서 바구니 확인하기
            if (!바구니.isEmpty() && doll == 바구니.peek()) {
                바구니.pop();
                answer++;
            } else {
                바구니.push(doll);
            }
        }

        return answer * 2;
    }
}

 

 

복기하기

저자 권장 시간	권장 시간 복잡도
60분	O(N^2 + M)

 

답안과 나의 풀이를 비교해보세요

import java.util.Stack;

class Solution {
    public int solution(int[][] board, int[] moves) {
	    // 각 열에 대한 스택을 생성
        Stack<Integer>[] lanes = new Stack[board.length]();
	    for (int i = 0; i < lanes.length; i++) {
		    lanes[i] = new Stack<>();
	    }

		// board를 역순으로 탐색하며 각 열의 인형을 lanes에 추가함
		for (int i = board.length - 1; i >= 0; i--) {
			for (int j = 0; j < board[i].length;j++) {
				if (board[i][j] > 0) {
					lanes[j].push(board[i][j]);
				}
			}
		}

		// 인형을 담을 buckt 생성
		Stack<Integer> bucket = new Stack<>();

		// 사라진 인형의 총 개수를 저장할 변수 초기화
        int answer = 0;

		// moves 순회하여 각 열에서 인형 뽑아 bucket 추가
        for (int move : moves) {
			if (!lanes[move-1].isEmpty()) {
				int doll = lanes[move - 1].pop();
				if (!bucket.isEmpty() && bucket.peek() == doll) {
					bucket.pop();
					answer += 2;
				} else {
					bucket.push(doll);
				}
			}
        }

        return answer;
    }
}

• 내 거가 더 예쁘다 호호
• 프로그래머스 다른 사람 풀이 보니까 나와 비슷한 생각을 한 사람이 많았다.

 

요약하기

• 답안의 시간 복잡도는 O(N^2 + M)이다
  • N은 board, M은 Moves
• 내 풀이의 시간 복잡도는 O(M * N) 아닐까