[Algorithm] 크레인 인형뽑기 게임

[hwangJi-dev]

📌 TODO

• 문제 풀이
• 정리

🍉 크레인 인형뽑기 게임

💬 Idea

1. moves 배열을 돌면서
   1. 게임보드의 칸 수만큼 for문을 돌아 크레인이 위치한 보드판 열에서 가장 윗칸에 위치한 인형을 뽑는다.
      1. 배열의 값이 0일 때는 인형이 없다는 의미이기 때문에 0이 아닌 숫자일 경우에 인형을 뽑는다.
   2. 인형을 뽑을 때 바구니(stack)의 최상단에 쌓여진 인형과 현재 뽑고자 하는 인형을 비교한다.
      1. 같은 인형일 경우
         1. 바구니에서 최상단에 쌓여진 인형을 제거한다.
         2. 카운트를 1 증가한다.
      2. 다른 인형일 경우
         1. 바구니에 현재 뽑고자 하는 인형을 쌓는다.
         2. 현재 크레인이 위치한 게임보드판의 값을 0으로 바꾼다.
         3. break한다.
2. 인형이 터진 횟수를 count에 저장했으므로 터진 인형의 개수를 구하기 위해 count에 2를 곱하여 결과를 리턴한다.
   1. 인형이 터질 때 2개씩 터지기 때문!

💬 막힌 부분

• 처음에 stack을 뽑아낼 때까지는 20분 남짓이 소요되었는데, stack에서 터진 인형의 개수를 뽑을 때 인형이 터지면 상단에 위치한 인형들이 내려와서 같은 인형을 만나 터질 수도 있다는 경우를 간과했다.
• 단순히 stack을 뽑아내어 같은 수가 2번 중복되어 위치하는 경우만 잡아내려고 하다가 문제의 요점이 그 것이 아님을 깨닫고 구현방향을 바꿨다.
• 문제를 똑바로 이해하는 것이 중요하다는 것을 깨닫게 되었다 !!

---

💬 풀이

func solution(_ board:[[Int]], _ moves:[Int]) -> Int {
    var gameBoard: [[Int]] = board
    var stack: [Int] = []
    var count: Int = 0
    
    for i in moves {
        for j in 0..<gameBoard.count {
            if gameBoard[j][i - 1] != 0 {
                if stack.last == gameBoard[j][i - 1] {
                    stack.removeLast()
                    count += 1
                } else {
                    stack.append(gameBoard[j][i - 1])
                }
                gameBoard[j][i - 1] = 0
                break
            }
        }
    }
    
    return count * 2
}

소요시간 : 57분 40초

---

💬 알게된 문법

✅  removeLast()

• collection의 마지막 요소를 제거한다.
• ⚠️ 빈 배열에 removeLast()를 적용하면 컴파일 에러가 나므로 주의하자 !
• 시간복잡도 : O(1)

✅  popLast()

• collection의 마지막 요소를 제거한다.
• removeLast와 달리 optional을 return한다.
  • 빈 배열에 popLast()를 적용하면 nil을 return한다. → 안전함
• 시간복잡도 : O(1)