[LeetCode] 394. Decode String(Kotlin)

[LeetCode] 394. Decode String(Kotlin)

• https://leetcode.com/problems/decode-string/

풀이 (정규표현식)

📌참고자료

• Kotlin StringBuilder - 문자열 효율적으로 다루기 | Notepad96
• 코틀린 에서 정규 표현식 사용하기 | GM.Lim
• MatchResult | Kotlin 공식 문서

• Regex.find 함수: 정규 표현식과 일치하는 첫번째 요소를 찾음, 반환 타입: MatchResult

class Solution {
    fun decodeString(s: String): String {
        val result = StringBuilder()
        var index = 0
        while(true){
            if(index < s.length) result.append(s[index])
            println("result: ${result.toString()}")

            while(true){
            	val match = Regex("""[0-9]+\[([a-z]+)\]""").find(result.toString())
                if (match == null) break
				
                println("matched value: ${match.value}")
                val matchRange = Pair(match.range.start, match.range.endInclusive)

            	val decoded = result.toString().substring(matchRange.first, matchRange.second+1)
                result.delete(matchRange.first, matchRange.second+1)
				println("result: ${result.toString()}")	

                val splitResult = decoded.split("[", "]")
                val count:Int = splitResult[0].toInt()
                val str:String = splitResult[1].toString()
                    	
                result.insert(matchRange.first, str.repeat(count)) 
        	}
            if(index > s.length) break
            else index++
        }
        return result.toString()
    }
}

• s = "2[abc]3[cd]ef"일 때 출력

  result: 2
  result: 2[
  result: 2[a
  result: 2[ab
  result: 2[abc
  result: 2[abc]
  matched value: 2[abc]
  result: 
  result: abcabc3
  result: abcabc3[
  result: abcabc3[c
  result: abcabc3[cd
  result: abcabc3[cd]
  matched value: 3[cd]
  result: abcabc
  result: abcabccdcdcde
  result: abcabccdcdcdef
  result: abcabccdcdcdef
  result: abcabccdcdcdef

• s = "3[a2[c]]"일 때 출력

  result: 3[
  result: 3[a
  result: 3[a2
  result: 3[a2[
  result: 3[a2[c
  result: 3[a2[c]
  matched value: 2[c]
  result: 3[a
  result: 3[acc]
  matched value: 3[acc]
  result: 
  result: accaccacc
  result: accaccacc

풀이 (스택)

import java.util.Deque

class Solution {
    fun decodeString(s: String): String {
        val st = ArrayDeque<Char>()

        var count = StringBuilder()
        var input = StringBuilder()
        s.forEach{ ch ->
            println("st: ${st.toString()}")

            if(ch == ']'){
                while(true){
                    val top = st.last()
                    println("parsing input... top: $top, st: ${st.toString()}")
                    if(top == '[') break
                    input.append(top)
                    st.removeLast()
                }

                st.removeLast() //remove '['

                while(!st.isEmpty()){
                    val top = st.last()
                    println("parsing count... top: $top, st: ${st.toString()}")
                    if(!(top in ('0'..'9'))) break
                    count.append(top)
                    st.removeLast()
                }
                
                val countInt = count.toString().reversed().toInt()
                val inputStr = input.toString().reversed()
                val decoded = inputStr.repeat(countInt)
                println("countInt: $countInt, inputStr: $inputStr, decoded: $decoded")
                
                decoded.forEach{ch -> st.addLast(ch)}

                count.setLength(0)
                input.setLength(0)
            }
            else st.addLast(ch)
        }

        return st.toList().joinToString(separator = "")
    }
}

• s = "2[abc]3[cd]ef"일 때 출력

  st: []
  st: [2]
  st: [2, []
  st: [2, [, a]
  st: [2, [, a, b]
  st: [2, [, a, b, c]
  parsing input... top: c, st: [2, [, a, b, c]
  parsing input... top: b, st: [2, [, a, b]
  parsing input... top: a, st: [2, [, a]
  parsing input... top: [, st: [2, []
  parsing count... top: 2, st: [2]
  countInt: 2, inputStr: abc, decoded: abcabc
  st: [a, b, c, a, b, c]
  st: [a, b, c, a, b, c, 3]
  st: [a, b, c, a, b, c, 3, []
  st: [a, b, c, a, b, c, 3, [, c]
  st: [a, b, c, a, b, c, 3, [, c, d]
  parsing input... top: d, st: [a, b, c, a, b, c, 3, [, c, d]
  parsing input... top: c, st: [a, b, c, a, b, c, 3, [, c]
  parsing input... top: [, st: [a, b, c, a, b, c, 3, []
  parsing count... top: 3, st: [a, b, c, a, b, c, 3]
  parsing count... top: c, st: [a, b, c, a, b, c]
  countInt: 3, inputStr: cd, decoded: cdcdcd
  st: [a, b, c, a, b, c, c, d, c, d, c, d]
  st: [a, b, c, a, b, c, c, d, c, d, c, d, e]

• s = "3[a2[c]]"일 때 출력

  st: []
  st: [3]
  st: [3, []
  st: [3, [, a]
  st: [3, [, a, 2]
  st: [3, [, a, 2, []
  st: [3, [, a, 2, [, c]
  parsing input... top: c, st: [3, [, a, 2, [, c]
  parsing input... top: [, st: [3, [, a, 2, []
  parsing count... top: 2, st: [3, [, a, 2]
  parsing count... top: a, st: [3, [, a]
  countInt: 2, inputStr: c, decoded: cc
  st: [3, [, a, c, c]
  parsing input... top: c, st: [3, [, a, c, c]
  parsing input... top: c, st: [3, [, a, c]
  parsing input... top: a, st: [3, [, a]
  parsing input... top: [, st: [3, []
  parsing count... top: 3, st: [3]
  countInt: 3, inputStr: acc, decoded: accaccacc