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

프로그래머스 Level1  2010 카카오 개발자 겨울 인턴십 문제

문제 설명 :  인형의 정보 board와 크레인 작동위치 moves가 주어질때, 크레인을 움직여 해당 인형을

바구니에 순차적으로 쌓고 같은 인형이 있다면 인형을 없애주고 없어진 인형의 개수를 카운트 하면된다.

그림에서 보는거처럼 바구니는 stack자료구조 특성을 이용하면 된다.

또한 크레인 위치가 주어질때 해당 열만 탐색해서 인형이 있다면 처리해주면 된다.

 

function solution(board, moves) {
  var answer = 0;
  //board 이차원 배열 깊은 복사
  let list = board.map((v) => v.slice());
  //바구니
  let stack = [];
  //크레인 위치정보만큼 반복
  for (let i = 0; i < moves.length; i++) {
    //배열의 인덱스 0부터 고려
    let n = moves[i] - 1;
    //크레인 위치 n을 기준으로 세로길이만큼만 탐색
    for (let j = 0; j < list.length; j++) {
      //배열에 인형이 있을시
      if (list[j][n] !== 0) {
        //바구니 마지막값이 현재 인형과 같다면
        if (stack[stack.length - 1] === list[j][n]) {
          answer += 2;
          stack.pop();
        }
        //다르면 인형 삽입
        else {
          stack.push(list[j][n]);
        }
        //뽑은 인형 처리후, 해당 배열 탐색 종료
        list[j][n] = 0;
        break;
      }
    }
  }
  return answer;
}

코드 설명 : 문제 설명과 주석에 적힌 설명 그대로 크레인 위치 정보에 해당하는 열을 탐색한다.

탐색 과정에서 인형을 발견하면 바구니에 넣기전에 바구니 마지막값과 비교하여 같다면 pop을 통해 마지막 인형을 없애주고 카운트 2를 해준다.

다르다면 바구니에 넣고 list해당위치를 0으로 초기화 한 후, 해당 열 탐색을 종료시킨다.

 

시간복잡도는 크레인위치 moves반복, board의 열 반복을 통해  O(n^2)이 된다.