[프로그래머스 LV.1] #31 크레인 인형뽑기 게임 (JavaScript)

💡 문제

크레인 인형뽑기 게임

 

🔍 분석 및 계획

✅ 문제 이해

NxN 크기의 다양한 종류의 인형이 들어있는 상자에서 인형뽑기기계를 사용해 위에서 부터 인형을 뽑아 바구니에 담는데 같은인형이 연속으로 담기면 인형이 터지게 된다. 터지는 인형의 개수를 구하는 문제이다.

• 입력 값 : 인형이 배치된 이차원 배열, 인형뽑기 기계작동 열순서 배열
  - 이차원 배열 = 5x5 ~30x30 크기
  - 이차원 배열 원소 = 0~100 이하 정수
  - 원소 0은 빈칸을 1~100은 각기 다른 종류의인형을 나타낸다
  - 열순서 배열의 크기는 1~1,000
  - 각 원소들은 1~가로크기 자연수 / 범위 이상의 값 없음
• 출력 값 : 터져 사라진 인형 개수

우선 각 열을 빼내는 순서가 스택구조이므로 각 뽑기 실행마다 검색하기 쉽도록 열중심 스택구조로 재배치 한다

1. 주어진 배열을 열 중심의 스택구조로 재저장한다
2. 뽑기 순서에 대한 반복문
   1. 각 열의 제일 최상단 값 가져오기
   2. 뽑았을 경우
      1. 바구니의 제일 위에 인형 확인하여 동일한 인형일 경우 제거, 제거 인형개수 +2
      2. 아닐경우 위에 올리기
3. 제거한 인형 개수 반환

 

✅ 의사코드 작성

//주어진 배열을 열 중심의 스택구조로 재저장한다
//뽑기 순서에 대한 반복문
  //각 열의 제일 최상단 값 가져오기
  //뽑았을 경우
    //바구니의 제일 위에 인형 확인하여 동일한 인형일 경우, 바구니에서제거하고  인형개수 +2
    //아닐경우 위에 올리기
//제거한 인형 개수 반환

 

 

📝 코드 구현

의사코드 + 코드

1. 숫자를 키값으로 사용하기 위해 Map 자료구조 사용

function solution(board, moves) {
  //주어진 배열을 열 중심의 스택구조로 재저장한다
  let machine = new Map();
  for(let i=1;i<=board.length;i++){
    machine.set(i,[]);
  }
  for(let i=board.length-1;i>=0;i--){
    for(let j=0;j<board[i].length;j++){
      if(board[i][j]!==0) machine.get(j+1).push(board[i][j]);
    }
  }
  let basket = [];
  let removed = 0;
  //뽑기 순서에 대한 반복문
  moves.forEach(x => {
    //각 열의 제일 최상단 값 가져오기
    if(machine.get(x).at(-1)) {
      //뽑았을 경우
      let picked = machine.get(x).pop();
      //바구니의 제일 위에 인형 확인하여 동일한 인형일 경우, 바구니에서제거하고  인형개수 +2
      if(picked === basket.at(-1)) {
        basket.pop();
        removed += 2;
      }
      //아닐경우 위에 올리기
      else basket.push(picked)
    }
  });
  //제거한 인형 개수 반환
  return removed;
}

 

최종 코드

1. removed 변수를 reduce함수에 넣어서 변수 개수를 줄여 주었다

function solution(board, moves) {
  let machine = new Map();
  for (let i = 1; i <= board.length; i++) {
    machine.set(i, []);
  }
  for (let i = board.length - 1; i >= 0; i--) {
    for (let j = 0; j < board[i].length; j++) {
      if (board[i][j] !== 0) machine.get(j + 1).push(board[i][j]);
    }
  }
  let basket = [];
  return moves.reduce((removed, position) => {
    if (machine.get(position).at(-1)) {
      let picked = machine.get(position).pop();
      if (picked === basket.at(-1)) {
        basket.pop();
        removed += 2;
      } else basket.push(picked);
    }
    return removed;
  }, 0);
}

시간 복잡도 : O(n²) => board 개수에 제한이 없을 시

 

💭 되돌아 보기

✅ 다른 사람 풀이

눈에 확 들어오는 풀이는 없었다