[javascript알고리즘] 크레인 인형뽑기 (카카오)

✅ 문제

https://school.programmers.co.kr/learn/courses/30/lessons/64061

✅ 접근방법

• stack에 인형을 쌓아가면서 새롭게 들어오는 인형과 가장 top에 있는 인형의 숫자를 비교하여 answer도출

👩🏻‍💻 풀이

function solution(boards, moves) {
  let answer = 0;
  let minusMove = moves.map((x) => x - 1); // 열번호 - 1
  let stack = []; // 인형을 담을 바구니

  minusMove.forEach((x) => {
    for (let i = 0; i < boards.length; i++) {
      if (boards[i][x] !== 0) {
        if (stack[stack.length - 1] === boards[i][x]) {
          answer += 2;
          stack.pop();
        } else {
          stack.push(boards[i][x]);
          boards[i][x] = 0;
        }
        break;
      }
    }
  });

  return answer;
}

let board = [
  [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],
];
let move = [1, 5, 3, 5, 1, 2, 1, 4];

console.log(solution(board, move));

• 인형의 위치는 1부터 시작하기 때문에 요소마다 -1 처리를 해준 minusMove배열을 새롭게 만들었다.
• minusMove배열을 돌면서 행 번호만 for문으로 계속 바꿔준다. (이중for문)
• boards[i][x] !== 0 : 인형이 존재할 때
  • stack[stack.length - 1] === boards[i][x] : 새롭게 들어오는 인형과 바구니 가장 상단의 인형이 같은 종류의 인형일 때 => answer += 2해주고 바구니에서 인형을 꺼낸다.
  • 같은 종류의 인형이 아닐 때 : stack에 인형을 추가해주고, 꺼낸 인형의 위치를 0으로 변경
• break
  • 이번 문제에서 가장 중요한 부분!!
  • 만약 break를 걸어주지 않으면 인형이 존재하는 부분을 모두 순회하기 때문에 원하는 위치의 인형을 찾았다면 break를 통해서 minusMove의 다음 요소로 넘어갈 수 있도록 해준다!

🤣 프로그래머스에서 다시 풀다가 발견한 에러!

function solution(boards, moves) {
  let answer = 0;
  let minusMove = moves.map((x) => x - 1); // 열번호 - 1
  let stack = []; // 인형을 담을 바구니

  minusMove.forEach((x) => {
    for (let i = 0; i < boards.length; i++) {
      // 인형이 존재하면
      if (boards[i][x] !== 0) {
        if (stack[stack.length - 1] === boards[i][x]) {
          answer += 2;
          stack.pop();
          boards[i][x];
        } else {
          stack.push(boards[i][x]);
          boards[i][x] = 0;
        }
        break;
      }
    }
  });

  return answer;
}

let board = [
  [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],
];
let move = [1, 5, 3, 5, 1, 2, 1, 4];

console.log(solution(board, move));

• 그 전에 코드에서는 stack의 마지막 값과 x값이 같으면 answer += 2해주고, pop()해주고 해당 위치의 값을 0으로 바꿔주지 않았다. 주어진 예제가 1개 밖에 없어서 몰랐는데, 프로그래머스에서 문제를 푸니까 2, 3, 4번을 제외하고는 모두 에러가 떠서 뭔가했는데 알고보니 0으로 바꿔주지 않았던 것이었다...
• 반례를 찾는 연습을 정말 많이 해야한다ㅜㅜ