간만의 알고리즘 공부 - 22 (크기가 작은 부분문자열)

문제 설명
숫자로 이루어진 문자열 t와 p가 주어질 때, t에서 p와 길이가 같은 부분문자열 중에서, 이 부분문자열이 나타내는 수가 p가 나타내는 수보다 작거나 같은 것이 나오는 횟수를 return하는 함수 solution을 완성하세요.
예를 들어, t="3141592"이고 p="271" 인 경우, t의 길이가 3인 부분 문자열은 314, 141, 415, 159, 592입니다. 이 문자열이 나타내는 수 중 271보다 작거나 같은 수는 141, 159 2개 입니다.

제한사항
- 1 ≤ p의 길이 ≤ 18
- p의 길이 ≤ t의 길이 ≤ 10,000
- t와 p는 숫자로만 이루어진 문자열이며, 0으로 시작하지 않습니다.

입출력 예 설명
입출력 예 #1
- 본문과 같습니다.

입출력 예 #2
- p의 길이가 1이므로 t의 부분문자열은 "5", "0", 0", "2", "2", "0", "8", "3", "9", "8", "7", "8"이며 이중 7보다 작거나 같은 숫자는 "5", "0", "0", "2", "2", "0", "3", "7" 이렇게 8개가 있습니다.

입출력 예 #3
- p의 길이가 2이므로 t의 부분문자열은 "10", "02", "20", "03"이며, 이중 15보다 작거나 같은 숫자는 "10", "02", "03" 이렇게 3개입니다. "02"와 "03"은 각각 2, 3에 해당한다는 점에 주의하세요

 

입출력 예

 

기본적으로 String 을 잘라서 비교해야한다는 생각으로 substring() 을 사용해서 해결하고자 생각했습니다

 

처음 푼 방법

class Solution {
    fun solution(t: String, p: String): Int {
        var lowerCount = 0
        val tSize= t.length
        val pSize= p.length
        val pValue = p.toInt()
        
        if (tSize == pSize) {
            if (pValue >= t.toInt()) {
                lowerCount++
            }
        } else {
            for (i in 0..(tSize-pSize)) {
                val tSubNum = t.substring(i, pSize+i)
                if (pValue >= tSubNum.toInt()) {
                    lowerCount++
                }
            }
        }
        
        return lowerCount
    }
}

 

 

 처음 풀었을때 로직에는 문제가 없다고 생각이 들었고 왜 문제가 발생했을까 계속 문제를 여러번 읽어봤습니다만, 입출력 예를 통해서 푸는 방법은 맞다고 생각이 들었습니다. 그래서 계속 생각하다가 런타임 에러가 발생할때 정수형 숫자의 범위로 인한 런타임 오류가 생각났고 t의 길이가 10,000 까지 가능하기에 이미 Int 의 범위를 벗어날 수 있겠구나라고 생각해서 숫자 변환 부분을 바꿔서 이슈를 수정했습니다

 

두번째 시도한 방법

class Solution {
    fun solution(t: String, p: String): Int {
        var lowerCount = 0
        val tSize= t.length
        val pSize= p.length
        val pValue = p.toDouble()
        
        if (tSize == pSize) {
            if (pValue >= t.toDouble()) {
                lowerCount++
            }
        } else {
            for (i in 0..(tSize-pSize)) {
                val tSubNum = t.substring(i, pSize+i)
                if (pValue >= tSubNum.toDouble()) {
                    lowerCount++
                }
            }
        }
        
        
        return lowerCount
    }
}

 

 

속도가 느리다고 판단해서 코드 첨삭을 받아봤는데, 다른것보다 Double, Long 의 차이에 의한 속도 차이도 꽤나 발생했습니다

코드 첨삭

class Solution {
    fun solution(t: String, p: String): Int {
        var lowerCount = 0
        val tSize = t.length
        val pSize = p.length
        val pValue = p.toLong()
        
        for (i in 0..(tSize - pSize)) {
            val tSubNum = t.substring(i, i + pSize).toLong()
            if (tSubNum <= pValue) {
                lowerCount++
            }
        }
        
        return lowerCount
    }
}

 

그리고 더불어서 다른 사람들의 코드도 확인해보았습니다. 역시 내장 함수를 잘 써서 만들면 이해하기도 쉽고 보기 편해보인 부분은 확실히 있었습니다. 다만, 속도가 확실히 느리다는 부분은 역시 항상 느끼는 부분입니다

 

다른 사람 코드

class Solution {
    fun solution(t: String, p: String): Int {
        return (0..t.length - p.length)
            .map{ t.substring(it until it + p.length) }
            .count { it <= p }
    }
}