파이썬, 자바스크립트_카카오 Lv.1 - 크레인 인형뽑기 게임

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

문제 요약:

N x N 크기의 정사각 격자
인형이 없는 곳에서 크레인을 작동시키는 경우에는 아무런 일도 일어나지 않습니다.
터트려져 사라진 인형의 개수를 return

제한:

2차원 배열로 크기는 "5 x 5" 이상 "30 x 30" 이하
각 칸에는 0 이상 100 이하인 정수가 담겨있습니다. 0은 빈 칸
moves 배열의 크기는 1 이상 1,000 이하

풀기 전 생각:

스택, 2차원 리스트
각 칸에 담겨있는 숫자의 종류는 시간 복잡도와 무관.
moves 1000번 이하로 돌면서, stack에 넣고, stack[-1]이랑 확인
시간복잡도 = O(N) 1초에 2000만번 연산을 하는 파이썬에겐 충분하다.

풀이 계획:

1. answer, stack 선언하고,
2. moves 돌면서,
   각 moves마다,
   board 길이 값 크기로 for 반복문
   0이 아니라면 stack에 넣고 0으로 바꿔주기.
3. stack에 넣을 때마다, stack 비어있는지 확인하고,
   비어있다면, 그냥 넣고
   비어있지 않다면, stack[-1]이랑 비교 후,
   같다면 stack.pop(), answer += 2
   같지 않다면, 추가
   stack.append()
   

---

풀이 코드

Python

def solution(board, moves):
  stack = []
  answer = 0
  n = len(board)

  for each_move in moves:
    for j in range(n):
      if board[j][each_move - 1] != 0:
        now = board[j][each_move - 1]
        if not stack:
          stack.append(now)
        else:
          if now == stack[-1]:
            stack.pop()
            answer += 2
          else:
            stack.append(now)
        board[j][each_move - 1] = 0
        break
  return answer

Javascript

function solution(board, moves) {
  const n = board.length;
  const stack = [];
  let answer = 0;


  for(let i=0; i<moves.length; i++){
    const outIndex = moves[i]-1;
    for(let j=0; j<n; j++){
      if(board[j][outIndex] != 0){
        if (board[j][outIndex] === stack[stack.length-1]){
          stack.pop();
          answer += 2
        } else{
          stack.push(board[j][outIndex]);
        }
        board[j][outIndex] = 0
        break
      }
    }
  }
  return answer;
}