[Level 1] 가장 가까운 같은 글자 - IntArray

내가 코딩한 아래 s1 메서드의 성능이 안 좋은 이유에 대해서 배운점을 리뷰해보려 한다.

// s의 길이가 10000일 때, 100.0ms / 197MB
fun solution1(s: String): IntArray { 
    var answer: IntArray = intArrayOf()
    var nearIndex = mutableMapOf<Char, Int>()

    for ((index, ch) in s.withIndex()) {
        val isContainsKey = nearIndex.containsKey(ch)
        answer += if(isContainsKey) index - nearIndex[ch]!! else -1
        nearIndex[ch] = index
    }
    return answer
}

// s의 길이가 10000일 때, 0.74ms / 70MB
fun solution2(s: String): IntArray { 
    val answer = IntArray(s.length)
    val nearIndex = IntArray(26) { -1 }

    for ((i, c) in s.withIndex()) {
        val charIndex = c - 'a'
        
        answer[i] = if (nearIndex[charIndex] == -1) nearIndex[charIndex] else i - nearIndex[charIndex]
        
        nearIndex[charIndex] = i
    }
    return answer
}

s1은 성능과 메모리 측면에서 높은 값이 나왔고, 어느 부분에서 차이가 있는지 확인하기 위해 다른 분의 s2 메서드를 가져와 비교했다.

 

- class s1과 s2의 차이점을 먼저 분석해보자.

차이점 1. s2는 answer을 필요한 길이만큼 먼저 할당을 했다. / s1은 빈 Array로 초기화한 뒤 += 연산자를 사용하여 값을 할당함

 

- GPT에게 성능과 메모리의 차이가 왜 났는지 물어봤다.

그 결과 "IntArray의 += 연산자는 매번 새 배열을 생성하여 복사하는 방식"으로 성능과 메모리 측면에서 효율이 좋지 않다는 피드백을 받을 수 있었다.

 

이후 확인을 위해 아래처럼 기존에 사이즈만큼 배열을 할당하고 값을 수정하는 방식으로 변경해봤다.

그러니 실행 시간과 메모리가 현저히 감소한 결과를 얻을 수 있었다.

// s의 길이가 10000일 때 5.4ms / 70MB
fun solution1(s: String): IntArray {
    var answer = IntArray(s.length) { -1 } // -1 default 값 지정
    var nearIndex = mutableMapOf<Char, Int>()

    for ((index, ch) in s.withIndex()) {
        if(nearIndex.containsKey(ch)) { // -1이 아닌 경우에만 값을 할당하도록 구현
            answer[index] =  index - nearIndex[ch]!!
        }
        nearIndex[ch] = index
    }
    return answer
}

 

차이점 2. s2는 (26)개의 배열을 미리 선언한 뒤 index와 ASCII Code 값을 활용하여 chars를 셋업한다.

마찬가지로 Pair<Char, Int> 타입으로 값을 먼저 초기화할 수는 없을까?

1~10 자연수 셋업에서 List(10) { it + 1 }과 같은 느낌으로 말이다.

 

- 방법 1. apply 메소드 사용하기

이런 방법도 있긴 하지만, 내가 추구했던 로직은 아니다.

val nearIndex = mutableMapOf<Char, Int>().apply {
    for (ch in 'a'..'z') {
        this[ch] = -1
    }
}
// ...

 

- 방법 2. associate 확장함수 사용하기

결과 : associate 메서드를 통해 List(n) { it + 1 } 과 같이 구현할 수 있었지만, 시간 차이는 크게 없었다.

fun solution1(s: String): IntArray {
    var answer = IntArray(s.length) { -1 }
    val nearIndex = (0 until 26).associate {
        ('a' + it) to -1
    }.toMutableMap()

    for ((index, ch) in s.withIndex()) {
        if(nearIndex[ch] == -1) {
            answer[index] =  index - nearIndex[ch]!!
        }
        nearIndex[ch] = index
    }
    return answer
}

 

 

- 배운점 : IntArray의 += 연산자는 매번 새 배열을 생성하여 복사하는 방식을 사용한다.

- 느낀점 : 앞으로 IntArray의 += 연산자는 쓸 일이 없을 것 같다. 써야한다면 mutableList()로 선언한 뒤에 값을 수정하고, .toIntArray()를 사용하자.