[프로그래머스]크레인 인형 뽑기 게임

문제 설명

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

게임 화면은 1 x 1 크기의 칸들로 이루어진 N x N 크기의 정사각 격자이며 위쪽에는 크레인이 있고 오른쪽에는 바구니가 있습니다. (위 그림은 5 x 5 크기의 예시입니다). 각 격자 칸에는 다양한 인형이 들어 있으며 인형이 없는 칸은 빈칸입니다. 모든 인형은 1 x 1 크기의 격자 한 칸을 차지하며 격자의 가장 아래 칸부터 차곡차곡 쌓여 있습니다. 게임 사용자는 크레인을 좌우로 움직여서 멈춘 위치에서 가장 위에 있는 인형을 집어 올릴 수 있습니다. 집어 올린 인형은 바구니에 쌓이게 되는 데, 이때 바구니의 가장 아래 칸부터 인형이 순서대로 쌓이게 됩니다. 다음 그림은 [1번, 5번, 3번] 위치에서 순서대로 인형을 집어 올려 바구니에 담은 모습입니다.

만약 같은 모양의 인형 두 개가 바구니에 연속해서 쌓이게 되면 두 인형은 터뜨려지면서 바구니에서 사라지게 됩니다. 위 상태에서 이어서 [5번] 위치에서 인형을 집어 바구니에 쌓으면 같은 모양 인형 두 개가 없어집니다.

크레인 작동 시 인형이 집어지지 않는 경우는 없으나 만약 인형이 없는 곳에서 크레인을 작동시키는 경우에는 아무런 일도 일어나지 않습니다. 또한 바구니는 모든 인형이 들어갈 수 있을 만큼 충분히 크다고 가정합니다. (그림에서는 화면표시 제약으로 5칸만으로 표현하였음)

게임 화면의 격자의 상태가 담긴 2차원 배열 board와 인형을 집기 위해 크레인을 작동시킨 위치가 담긴 배열 moves가 매개변수로 주어질 때, 크레인을 모두 작동시킨 후 터트려져 사라진 인형의 개수를 return 하도록 solution 함수를 완성해주세요.

[제한사항]

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

풀이

1. 접근하기

​ 우선, 어떤 것을 입력 받는지 살펴 보았다. 2차원 배열 을 입력 받으니 2차원 배열을 for 문을 돌려서 1번 , 2번 , 3번 ... N번 열에 저장 되도록 행과 열을 바꿨다. 바꿔줄때 0이 저장되어있는 곳은 없애 주었다. 각각의 배열들이 stack 개념이라고 생각하였다.

나중에 stack 자료구조를 더 깊게 공부하고 이 문제를 다시 풀어보자.

처음에는, 뽑으면서 처음 뽑은 것과 나중 뽑은 것을 비교하면서 같아지면 anwser의 카운트가 2개씩 올라가는 구조로 설계하려 하였으나, 기존에 쌓여있는 것과 만나서 사라지는 경우도 있으므로 바구니에 저장되는 인형들을 배열에 저장하는게 좋다고 판단 하였다.

다음으로는 moves 에 있는 명령 만큼 모두 바구니 배열에 옮겨 닮은 다음, 같은 인형들을 사라지게 하는 check 함수를 만들었다. 문제는 배열을 slice 할 때 마다 배열의 상태가 달라지기 때문에 한번의 함수제어로 return 값을 내기 어려웠다. 그렇기 때문에 재귀함수로 만들어 같은 인형이 없을 때 배열을 return 하는 방식을 생각해 냈다.

2. detail

stack

• 정의: 스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조로 되어있고, 나중에 넣은 값이 먼저 나오는 LIFO 구조입니다.
  https://ko.wikipedia.org/wiki/%EC%8A%A4%ED%83%9D

Stack 주요 연산

• S.top(): 스택의 가장 윗 데이터를 반환한다. 만약 스택이 비었다면 이 연산은 정의불가 상태이다.
• S.pop(): 스택의 가장 윗 데이터를 삭제한다. 스택이 비었다면 연산 정의불가 상태.
• S.push(): 스택의 가장 윗 데이터로 top이 가리키는 자리 위에(top = top + 1) 메모리를 생성, 데이터 x를 넣는다.
• S.empty(): 스택이 비었다면 1을 반환하고,그렇지 않다면 0을 반환한다.

JS class (ES6) 으로 Stack 구현해 보기

• Array 를 사용하여 Stack 을 구현할 수 있습니다.
• Array의 push() , pop() 메소드를 사용합니다.
• push() 는 Array에 맨 끝 index 에 데이터를 넣습니다.
• pop() 은 Array에 맨 끝에 있는 data를 빼옵니다.

class Stack {
  constructor() {
    this.store = [];
  }
  
  push(item) {
    this.store.push(item);
  }
  
  pop() {
    return this.store.pop();
  }
}

const stack = new Stack();
stack.push(1);
stack.push(2);
stack.pop();   // 2

재귀 함수(recursion function)

recursion 함수 작성법

1. 함수의 순환되는 구조를 파악
   • factorial의 경우 n을 곱하고 factorial(n-1)이 반복적으로 사용됩니다.
   • 반복되는 구조를 알기 위해 함수의 진행사항을 코드로 만들어보면 알기 쉽습니다.
2. Base case, termination case : 끝내는 구간을 설정
   • 끝내는 구조를 설정하지 않으면 무한루프에 빠집니다.
   • if를 통해 걸어주면 끝나는 구간이 설정되어 이후 과정이 시작됩니다.

recursion 함수 원리

• Recursion 함수는 stack 원리를 가지고 있습니다.
• stack 의 경우 성질에 따라 먼저 들어간 stack 은 후에 들어간 stack이 끝나기 전까지 종료 될수 없습니다.

recursion 함수 장 단점

장점

• 타 개발자가 알아보기 쉽다. (인간 위주 함수)

단점

• 브라우저 마다 stack 수의 한계가 존재. stack 한계 도달시 recursion 사용 못함
• stack 은 브라우저의 메모리를 사용한다. 즉, stack 을 많이 쓸 수록 웹의 성능 저하 (but 하드웨어의 성능은 좋으니 startup의 경우 해당사항 없음)

array.splice(start, deleteCount, item) vs array.slice(start[, end])

• slice() 메소드는 begin부터 end 전까지의 복사본을 새로운 배열 객체로 반환한다. 즉, 원본 배열은 수정되지 않는다.

• splice() 메소드는 배열의 기존 요소를 삭제 또는 교체하거나 새 요소를 추가하여 배열의 내용을 변경한다. 이 메소드는 원본 배열 자체를 수정한다.

var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

var arr1 = arr.slice(3, 5); // [4, 5] // arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]



var arr1 = arr.splice(10, 2, 'a', 'b', 'c');


console.log(arr); // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, "a", "b", "c"]
console.log(arr1); // [11, 12]

3. 실수한 부분

​

​ 문제 조건을 제대로 보지 않았다. 입력 되는 2차원 배열이 항상 5X5 배열인 줄 알았는데 다시 읽어 보니 NXN 배열이였다. 이 문제를 해결하는데 1시간이나 걸렸으니... 굉장한 삽질을 한것이다. 실제 시험에서는 test case 가 충분치 않게 주기 때문에 이를 알아채지 못했을 것이다. 특히 입력 부분은 제한 사항을 주의 깊게 살펴볼 필요가 있다.

4. code

function solution(board, moves) {
  var answer = 0;
  let array = [];
  let len = board.length
  for (let i = 0; i < len; i++) {
    let temp = [];
    for (let j = 0; j < len; j++) {
      if (board[j][i] != 0) {
        temp.push(board[j][i]);
      }
    }
    array.push(temp);
  }

  const pickUp = (temp, num) => {
    if (array[num].length != 0) {
      temp.push(array[num].shift());
    }
    return temp;
  };

  var tem = [];
  var temps = pickUp(tem, moves[0] - 1);
  var l = 0;

  for (let k = 1; k < moves.length; k++) {
    const num = moves[k] - 1;
    temps = pickUp(temps, num);
  }

  const check = (temp) => {
    for (let i = 0; i < temp.length - 1; i++) {
      if (temp[i] === temp[i + 1]) {
        answer = answer + 2;
        temp.splice(i, 2);
        return check(temp);
      }
    }

    return temp;
  };

  check(temps);

  return answer;
}