프로그래머스 - 햄버거 만들기

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

 

처음 작성했던 코드

fun solution(ingredient: IntArray): Int {
    var count = 0
    var ingredientText = ingredient.joinToString("")
    while (ingredientText.contains("1231")) {
        val replaced = ingredientText.replaceFirst("1231", "")
        if (ingredientText != replaced) {
            ingredientText = replaced
            count++
        }
    }
    return count
}

 

찾아보며 수정한 코드

fun solution(ingredient: IntArray): Int {
    var count = 0
    val builder = StringBuilder()
    for (element in ingredient) {
        builder.append(element)
        val length = builder.length
        if (length > 3 && builder.subSequence(length - 4, length) == "1231") {
            builder.delete(length - 4, length)
            count++
        }
    }
    return count
}

 

처음에 풀었던 코드는 ingredient를 joinToString으로 String으로 변환 후
"1231"이 포함되어 있지 않을 때까지 while문을 돌려 count를 구하는 방식이었다.

 

해당 코드로 프로그래머스에서 채점을 돌렸는데 시간 초과가 떴다.

분명 로직상 문제는 없어보이는 코드여서 구글에 해당 문제에 관련하여 검색해보았다.

 

어느 한 블로그에서 나와 거의 비슷한 코드가 있었는데 해당 문제에서 사용할 수 없는 방식이라고 설명되어 있었다.

joinToString 메서드도 내부에서 for문을 돌리는 것이기 때문에
for문과 while문 두개를 사용하니 로직이 무거워져 시간 초과가 떴던 것이다.

 

두번째 코드에선 StringBuilder를 사용하여 for문을 하나로 줄여 엘리먼트를 넣어줌과 동시에 조건을 체크하여

조건이 맞으면 1231을 지우고 count를 추가하는 방식으로 바꾸었더니 속도도 빨라졌고 시간초과도 뜨지 않았다.

 

평소 코틀린에서 아무렇게 쓰지 않던 확장함수들의 내부 코드를 다시 한번 생각해보면서
시간 복잡도를 좀 더 익혀야겠다는 생각이 들었다.