크레인 인형뽑기 게임
2019 카카오 개발자 겨울 인턴십 (1. 크레인 인형뽑기 게임) | 프로그래머스
문제
게임 화면은 "1 x 1" 크기의 칸들로 이루어진 "N x N" 크기의 정사각 격자이며 위쪽에는 크레인이 있고 오른쪽에는 바구니가 있습니다. (위 그림은 "5 x 5" 크기의 예시입니다).
각 격자 칸에는 다양한 인형이 들어 있으며 인형이 없는 칸은 빈칸입니다.
모든 인형은 "1 x 1" 크기의 격자 한 칸을 차지하며 격자의 가장 아래 칸부터 차곡차곡 쌓여 있습니다. 게임 사용자는 크레인을 좌우로 움직여서 멈춘 위치에서 가장 위에 있는 인형을 집어 올릴 수 있습니다.
집어 올린 인형은 바구니에 쌓이게 되는 데, 이때 바구니의 가장 아래 칸부터 인형이 순서대로 쌓이게 됩니다.
다음 그림은 [1번, 5번, 3번] 위치에서 순서대로 인형을 집어 올려 바구니에 담은 모습입니다.
만약 같은 모양의 인형 두 개가 바구니에 연속해서 쌓이게 되면 두 인형은 터뜨려지면서 바구니에서 사라지게 됩니다.
위 상태에서 이어서 [5번] 위치에서 인형을 집어 바구니에 쌓으면 같은 모양 인형 두 개가 없어집니다.
크레인 작동 시 인형이 집어지지 않는 경우는 없으나 만약 인형이 없는 곳에서 크레인을 작동시키는 경우에는 아무런 일도 일어나지 않습니다.
또한 바구니는 모든 인형이 들어갈 수 있을 만큼 충분히 크다고 가정합니다.
(그림에서는 화면표시 제약으로 5칸만으로 표현하였음)
게임 화면의 격자의 상태가 담긴 2차원 배열 board와 인형을 집기 위해 크레인을 작동시킨 위치가 담긴 배열 moves가 매개변수로 주어질 때, 크레인을 모두 작동시킨 후 터트려져 사라진 인형의 개수를 return 하도록 solution 함수를 완성해주세요.
흐름 생각하기
스택의 pop과 비슷한 형태라고 생각했다.맨 위에 쌓인 인형들이 먼저 떠나감 ▶ 불려간 순서에 따라 인형이 배치됨 ▶ 같은 인형끼리 붙어있으면 사라짐
입출력의 예시를 보자
[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]
처음에 board에 인형들이 이렇게 배치되어있다.
뽑는 순서는 [1,5,3,5,1,2,1,4] 니까
4 ▶ 3 ▶ 1 ▶ 1 ▶ 3 ▶ 2 ▶ (아무일 생기지 않음) ▶ 4
여기서 1이 중복되어 겹치니까 사라지게 된다
4 ▶ 3 ▶ 3 ▶ 2 ▶ 4
사라지게 되면서 위에 있던게 아래로 내려가게 되니까 또 3이 중복되어 겹치니까 사라진다.
4 ▶ 2 ▶ 4
1,1,3,3 이렇게 총 4개가 사라지니까 반환되는 값은 4가 된다.
문제내용과 입출력 예시는 이해가 되었다.
이제 어떻게 코드를 짜야하는 걸까
코드 어떻게 짜야할까
board와 moves가 매개변수인 함수를 짜라고 했다. board는 이차원 배열이고 moves는 일차원 배열이다.board의 크기는 1 <= board <=1,000
moves 배열의 크기는 1 <= moves <= board 배열의 가로 크기 이하인 자연수
아무래도 실행시간때문에 범위를 제한한 것 같다. 근데 내가 코드를 짤 때 고려할만한 사항인가?
제일 간단한 방법은 board를 중심으로 moves 배열의 원소대로 인형을 빼간다.
그 후 인형을 담을 바구니 리스트를 하나 만들어주고, 빼간 인형을 바구니 리스트에 넣어준다.
리스트에 넣어줄 때마다 맨 뒤의 함수의 원소와 같은지 비교해준다
(stack과 같은 느낌이니까 리스트 상 맨 뒤에 있는 인형이 맨 위에 있는 것과 같기 때문)
만약에 같을 경우 해당 원소를 삭제해준 뒤, answer 값에 2씩 더해준다.
앞의 출력 예시처럼 인형들이 사라지면서 위에 있던 인형이 내려오다가 또 중복이 생겨서 사라지는 경우가 있을 것이다. 그 경우를 놓쳐선 안될 것같다.
코드 짜보기
처음에 막 써본 코드는 다음과 같다. 결과는 index 범위가 맞지않은 런타임 에러
아 생각해보니까 내가 가로로 뽑는걸로 생각을 해버렸구나 싶다.
board에 접근하는 방법이 틀렸다. 행이 아니라 열이었다.
열로 접근하도록 바꿨더니 일단 바구니에 들어가는 인형 순서는 맞게 들어갔다. 이제 문제는 가까이 있는 애들을 어떻게 삭제할 것이냐.. 버블정렬..? 일단 서로 원소를 비교해나가면서 원소를 지우니까 index 관련 에러가 나게 된다. 이 부분만 어떻게 해주면 될듯
최종코드
간만에 알고리즘 문제를 풀려고 하니 엄청 버벅거리고 효율적인 코드가 나오진 않았다.
난도가 매우 낮은 문제이지만 그래도 풀었으니 매우 뿌듯하다.
다 풀었다고 끝나는 게 아니라 나중에 다른분들의 코드도 보면서 비교해봐야겠다. 충분히 짧게 나올 수 있는 코드 같은데 지금 생각이 나질 않는다😂
.gif)