크레인 인형뽑기(카카오 기출) : Stack

첫 풀이

function solution(board, moves) {
  let answer = 0;
  let stack = [];
  moves.forEach((pos) => {
    for (let i = 0; i < board.length; i++) {
      if (board[i][pos - 1] !== 0) {
        let tmp = board[i][pos - 1];
        board[i][pos - 1] = 0;
        if (tmp === stack[stack.length - 1]) {
          stack.pop();
          answer += 2;
        } else stack.push(tmp);
        break;
      }
    }
  });

  return answer;
}

let a = [
  [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 b = [1, 5, 3, 5, 1, 2, 1, 4];
console.log(solution(a, b));

이중 for문으로 O(N^2)의 시간복잡도

수정된 풀이

function solution(board, moves) {
  let answer = 0;
  let stack = [];
  
  let pos = []; // 각 열의 맨 위의 인형 위치
  for (let y in board[0]) {
    if (board[board.length - 1][y] === 0) {
      // 빈 열이면 해당 열의 pos값은 -1
      pos.push(-1);
      continue;
    } else {
      // 빈 열이 아니면 맨 위의 인형 pos에 저장
      for (let x in board) {
        if (board[x][y]) {
          pos.push(Number(x));
          break;
        }
      }
    }
  }

  for (let t of moves) {
    let y = t - 1;
    // 해당 열에 인형이 없으면 스킵
    if (pos[y] === -1) continue;
    else {
      // 해당 열에 인형이 있으면
      let doll = board[pos[y]][y];
      if (stack.length && stack[stack.length - 1] === doll) {
        stack.pop();
        answer += 2;
      } else stack.push(doll);
      if (pos[y] === board.length - 1) pos[y] = -1;
      else pos[y] += 1;
    }
  }
  return answer;
}

let a = [
  [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 b = [1, 5, 3, 5, 1, 2, 1, 4];
console.log(solution(a, b));

시간복잡도를 낮춰보고자 pos라는 배열을 따로 만들었다.

개선할 수 있는 점

• if (pos[y] === -1) continue; 부분을 제거하고 그냥 else 부분을 if로 감쌌으면 좀 더 간결했을 것 같다.

Solution 풀이

function solution(board, moves) {
  let answer = 0;
  let stack = [];
  moves.forEach((pos) => {
    for (let i = 0; i < board.length; i++) {
      if (board[i][pos - 1] !== 0) {
        let tmp = board[i][pos - 1];
        board[i][pos - 1] = 0;
        if (tmp === stack[stack.length - 1]) {
          stack.pop();
          answer += 2;
        } else stack.push(tmp);
        break;
      }
    }
  });

  return answer;
}

let a = [
  [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 b = [1, 5, 3, 5, 1, 2, 1, 4];
console.log(solution(a, b));

배운 점

• forEach 함수에 대해서 좀 더 찾아보면서 알게 되었다.
  (하지만 x, y 좌표의 관점에서는 차라리 이중 for문을 쓴 내 코드가 좀 더 직관적이였던 것 같다.)