[Algorithm - Stack] Kotlin - programmers Lv1 [ 크레인 게임 ]

[ Algorithm Link ]

프로그래머스

---

 

최종 코드 미리보기

 

import java.util.Stack

private fun solution(board: Array<IntArray>, moves: IntArray): Int {
    var answer = 0
    var stack = Stack<Int>()

    moves.forEach {
        for (i in board.indices) {
            if (board[i][it - 1] != 0) {
                if (stack.isNotEmpty() && stack.peek() == board[i][it - 1] ) {
                    stack.pop()
                    answer += 2
                } else {
                    stack.push(board[i][it - 1])
                }
                board[i][it - 1] = 0

                break
            }
        }
    }
    return answer
}

 

[ 코드 나눠보기 ]

• if ( board[i][it - 1 ] != 0 )➡️보드를 시각화 했을 때, 위에 행에서 부터 각 moves 에 포함된 숫자를 포함하는 열의 값이 0이 아닐 경우 다음 if 문 로직이 실행된다.
• if ( stack.isNotEmpty() && stack.peek() == board[i][it - 1]) 스택이 비어있는 경우 peek이 예외를 반환하여, 스택이 비어있지 않으면 Stack의 가장 위의 값을 확인 후 넣으려는 값과 동일하면 Stack의 가장 위 수를 제거하고 answer + 2 
• 스택이 비어있거나, 스택의 가장 위의 수가 넣으려는 숫자와 같지 않을 경우 스택에 값을 추가해준다.
• board[i][it - 1] = 0 움직인 인형의 원래 위치는 인형이 없는 상태인 0 값을 지정해주고 break 로 인형 1개를 옮기는 할달량을 채운 moves 값의 forEach 반복을 종료해준다.

 

 

 

제출 코드 - 통과 → 리팩토링 전

 

import java.util.LinkedList
import java.util.Queue
import java.util.Stack

fun solution(board: Array<IntArray>, moves: IntArray): Int {
    var answer = 0

    var queueList = mutableListOf<Queue<Int>>()

    for (i in board.indices) {
        var queue = LinkedList<Int>()

        board.forEach {
            if (it[i] != 0) {queue.add(it[i])}
        }

        queueList.add(queue)
    }
    
    var basket = Stack<Int>()

    moves.forEach {
        queueList[it-1].poll()?.let { num ->
            if ( basket.isEmpty()) {
                basket.push(num)
            } else if (basket.peek() == num) {
                basket.pop()
                answer+= 2
            } else {
                basket.push(num)
            }
        }
    }
    return answer
}

 

 

 

[ 작성코드 정리]

 

1. 보드배열을 List<Queue>자료구조로 만들기

    var queueList = mutableListOf<Queue<Int>>()

    for (i in board.indices) {
        var queue = LinkedList<Int>()

        board.forEach {
            if (it[i] != 0) {queue.add(it[i])}
        }

        queueList.add(queue)
    }

 

• board의 각 열에는 인형이 쌓여져 있고, 인형을 뽑게되면 보드에 인형이 사라지므로, Queue 자료구조 특성에 알맞는다고 생각되어서 board 배열을 Queue로 바꿔주는 작업을 진행했다.
  • 🟥 2차원 배열 board의 행,렬을 바꾸어 List<Queue>로 다시 만들게 되어서 O(n^2)의 시간복잡도를 갖게 되었다. 단순히 배열 바꾸려고 성능이 많이 떨어져서 리팩토링 시 다른 코드 방식으로 변경.

 

 

2. 인자로 받은 moves를 통해 Stack에 인형값 넣고, 비교하기

   var basket = Stack<Int>()
   
    moves.forEach {
        queueList[it-1].poll()?.let { num ->
            if ( basket.isEmpty()) {
                basket.push(num)
            } else if (basket.peek() == num) {
                basket.pop()
                answer+= 2
            } else {
                basket.push(num)
            }
        }
    }

• ?.let {} 으로 널 예외처리 하여, 크레인으로 집으려는 보드의 열에 인형이 있을 때에만 인형을 바구니로 옮기는 로직이 동작하도록 함.
• Stack 자료구조 인터페이스를 통해 마지막으로 넣은 값이 넣으려는 값과 동일할 경우, push() 하지 않고 pop() 함으로 직전에 넣어둔 값만 제거하고 answer에 2를 더해준다.

 

[ 계산 복잡도 ]

시간 복잡도 = O(n^2) ➡️ board의 행, 열을 각각 구분하지 않고 board 전체로 queueList 을 만들게 되어, 높은 복잡도를 갖게 되었다.

공간 복잡도 = O(n^2) ➡️ 시간복잡도와 동일한 이유.

 

 

 

 

알고리즘 회고

 

알고리즘을 풀다보면, 코드 전반적인 가독성도 떨어지고 계산 복잡도 등을 신경쓰지 못하고 코드를 작성하는 것 같다. 꾸준히 알고리즘을 푼 다음에 잘 작성된 다른 사람들의 코드를 보고 비교해보면서 학습 해봐야겠다.

 

★ 구조를 잘 만드는 연습 ★

 

 

 

 

 

 

---

[Reference]