[Level 1] 햄버거 만들기 Stack vs MutableList, 시간 비교(요소 삽입, 제거 및 인덱스접근)

[내배캠 - 오늘의 문제]

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

프로그래머스

문제 접근 base. 입력받은 Array의 값을 순회하며 stack에 쌓는다.

문제 접근 point1. stack의 peek()값이 1일 때, 상위 4개의 요소를 뽑아 "1321"과 같은지 비교한다. 같다면, answer++ 및 stack.pop() * 4번 수행

 

 

코드는 아래와 같다.

(길어서 접어둠)

// Stack 버전
class Solution {
    fun solution(ingredient: IntArray): Int {
        var answer: Int = 0
        var stack = Stack<Int>()

        for (num in ingredient) {
            stack.push(num)

            if (stack.size < 4 || num != 1) {
                continue
            }

            var sb = StringBuilder()

            for (i in 1..4) {
                sb.append(stack[stack.size - i])
            }

            if (sb.toString() == "1321") {
                repeat(4) {
                    stack.pop()
                }
                answer++
            }
        }
        return answer
    }
}

// MutableList 버전
class Solution1 {
    fun solution(ingredient: IntArray): Int {
        var answer: Int = 0
        var stack = mutableListOf<Int>()

        for (num in ingredient) {
            // TODO: peek() 값이랑 num값이랑 같은 경우, add 할 필요가 없음 ex) 22, 33, 44
            stack.add(num)

            if (stack.size < 4 || num != 1) {
                continue
            }

            var sb = StringBuilder()

            for (i in 1..4) {
                sb.append(stack[stack.size - i])
            }

            if (sb.toString() == "1321") {
                repeat(4) {
                    // 프로그래머스는 같은 코드여도 시간차이가 많이 날 때가 있었음 (확실히 인터넷 속도 등의 영향을 많이 받는 것 같다.)
                    // 프로그래머스 기준 : removeLast()가 2배 더 느렸음
                    stack.removeAt(stack.size - 1)
                }
                answer++
            }
        }
        return answer
    }
}

처음엔 스택으로 구현했지만, 추후 시간 단축을 위해 변경하다보니 Stack이 아닌 MutableList로 변경해보았는데 재밌는 결과가 나왔다.

테스트를 위해 100만개의 무작위 1~3 숫자를 생성한 뒤, 동일한 데이터를 Stack타입과 MutableList에 각각 태워보니 생각보다 많은 차이가 있었다.

(프로그래머스 상에서는 별로 차이 나지 않았었는데 로컬에서 랜덤 숫자로 테스트 하니 차이가 많이 난다.)

fun main() {
    val data = List(1_000_000) {
        Random.nextInt(3) + 1
    }

    val time1 = System.nanoTime()
    
    Solution().solution(data.toIntArray()) // Stack
    
    val time2 = System.nanoTime()
    
    Solution1().solution(data.toIntArray()) // MutableList
    
    val time3 = System.nanoTime()
    
    println(time2 - time1) //       Stack, 66432700
    println(t1me3 - time2) // MutableList, 39019600
}

 

두 코드의 차이점은 단순히 요소 추가, 삭제, 인덱스 접근의 차이밖에 없었다.

 

당연히 MutableList보단 Stack이 더 좋은 효율을 보일거라고 생각했지만, 결과는 반대였다..

 

정리 : Stack의 push(), pop(), [index] 보다 MutableList의 add(), removeAt(), [index] 가 더 빨랐음

 

 

의미가 있을지 모르겠지만 개인적으로 궁금해서 각 시간을 비교해보았다.

(과정은 아래에 있는 더보기 클릭)

import kotlin.time.measureTime

fun main() {
    var mutableList = mutableListOf<Int>()

    val data = List(1_000_000) {
        Random.nextInt(3) + 1
    }

    val mutableListAdd = measureTime {
        for (num in data) {
            mutableList.add(num)
        }
    }

    val mutableListIndex = measureTime {
        for (i in data.indices) {
            mutableList[i]
        }
    }

    val mutableListRemoveLast = measureTime {
        for (num in data) {
            mutableList.removeLast()
        }
    }

    for (num in data) {
        mutableList.add(num)
    }

    val mutableListRemoveAt = measureTime {
        for (num in data) {
            mutableList.removeAt(mutableList.size - 1)
        }
    }
}

 

기준은 랜덤 숫자 100만 개에 대해 추가, 인덱스 접근, 삭제를 수행했다.

// 1. 요소 추가
println(stack Push)             // 20.831ms
println(mutableList Add)        // 10.856ms

// 2. 인덱스 접근
println(stack Index)            // 14.134600ms
println(mutableList Index)      //  3.349200ms

// 3. 요소 삭제
println(stack RemoveLast)       // 19.61400ms
println(stack RemoveAt)         // 16.5078ms
println(stack Pop)              // 16.066700ms

println(mutableList RemoveLast) //  9.46900ms
println(mutableList RemoveAt)   //  4.9997ms

 

혹시 몰라 랜덤 숫자 1억 개에 대해 추가, 인덱스 접근, 삭제를 수행했다.

-> 사실 짠 코드가 아까워서 테스트 해봄,,, ㅋㅋㅋㅋ

// 1. 요소 추가
println(stack Push)             // 2301.9695ms
println(mutableList Add)        //  847.1057ms

// 2. 인덱스 접근 - 엄청난 차이..
println(stack Index)            // 1384.521ms
println(mutableList Index)      //   37.968ms  1억 개의 요소에 인덱스로 접근하는데 37ms?! 와,,, 쩐다

// 3. 요소 삭제 - 엄청난 차이.. 22
println(stack Pop)              // 1416.335ms

println(mutableList RemoveLast) //  140.0605ms
println(mutableList RemoveAt)   //  134.8008ms

 

확실히 stack에서 인덱스를 통해 요소에 접근하는 로직이 시간 차이가 많이 났다.

 

stack[i]로 접근 시, Stack(Vector.java)에는 인덱스 지원이 없으므로 List(Collection.kt)를 호출하는 것으로 확인 됐다. 그래서 오래 걸린 듯!!!

-> Stack 타입에 index 접근을 하면, Stack을 사용하지 않는 것을 넘어 mutableList보다 훨씬 느리게 수행된다는 점을 확인할 수 있었다.

 

- 그래서 시도해봄 -> 인덱스로 접근하지 않고, pop()으로 빼서 4개의 요소와 "1321"을 비교한 뒤, 아닌 경우 다시 push()하도록 하니 전체 로직의 수행 시간이 배로 증가함 ㅎㅎㅎㅎㅎ 이건 아닌 듯

 

 

마지막!! 새로운 시간 측정 메서드 발견

import kotlin.time.measureTime

val stackPush = measureTime  {
    for (num in data) {
        stack.push(num)
    }
}

measureTime 메서드의 리턴값은 수행된 Duration에 따라서 자동으로 s, ms, us 등으로 단위 변환을 해준다.

 

 

 

풀코드

import java.util.*
import kotlin.random.Random
import kotlin.time.measureTime

fun main() {
    val data = List(100_000_000) {
        Random.nextInt(3) + 1
    }

    var stack = Stack<Int>()

    val stackPush = measureTime  {
        for (num in data) {
            stack.push(num)
        }
    }

    val stackIndex = measureTime  {
        for (i in data.indices) {
            stack[i]
        }
    }

    val stackPop = measureTime  {
        for (num in data) {
            stack.pop()
        }
    }

    var mutableList = mutableListOf<Int>()

    val mutableListAdd = measureTime  {
        for (num in data) {
            mutableList.add(num)
        }
    }

    val mutableListIndex = measureTime  {
        for (i in data.indices) {
            mutableList[i]
        }
    }

    val mutableListRemoveLast = measureTime  {
        for (num in data) {
            mutableList.removeLast()
        }
    }

    for (num in data) {
        mutableList.add(num)
    }

    val mutableListRemoveAt = measureTime  {
        for (num in data) {
            mutableList.removeAt(mutableList.size - 1)
        }
    }


    println(stackPush)  // 2.301969500s
    println(stackIndex) // 1.384521s
    println(stackPop)   // 1.416335s
    println()

    println(mutableListAdd)        // 847.105700ms
    println(mutableListIndex)      //  37.968300ms
    println(mutableListRemoveLast) // 140.060500ms
    println(mutableListRemoveAt)   // 134.800800ms
}