간만의 알고리즘 공부 - 23 (가장 가까운 같은 글자)

문제 설명
문자열 s가 주어졌을 때, s의 각 위치마다 자신보다 앞에 나왔으면서, 자신과 가장 가까운 곳에 있는 같은 글자가 어디 있는지 알고 싶습니다.예를 들어, s="banana"라고 할 때,  각 글자들을 왼쪽부터 오른쪽으로 읽어 나가면서 다음과 같이 진행할 수 있습니다.
b는 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다.a는 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다.n은 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다.a는 자신보다 두 칸 앞에 a가 있습니다. 이는 2로 표현합니다.n도 자신보다 두 칸 앞에 n이 있습니다. 이는 2로 표현합니다.a는 자신보다 두 칸, 네 칸 앞에 a가 있습니다. 이 중 가까운 것은 두 칸 앞이고, 이는 2로 표현합니다.
따라서 최종 결과물은 [-1, -1, -1, 2, 2, 2]가 됩니다.
문자열 s이 주어질 때, 위와 같이 정의된 연산을 수행하는 함수 solution을 완성해주세요.

제한사항
- 1 ≤ s의 길이 ≤ 10,000
    - s은 영어 소문자로만 이루어져 있습니다.

 

입출력 예

 

 

내가 푼 방법

class Solution {
    fun solution(s: String): IntArray {
        val answer = mutableListOf<Int>()
        val map = mutableMapOf<Char, Int>()
        
        for (i in s.indices) {
            if (map.containsKey(key = s[i])) {
                answer.add(i - map.get(key = s[i])!!)
            } else {
                answer.add(-1)
            }
            map.put(s[i], i)
        }
    
        return answer.toIntArray()
    }
}

 

일단 점수가 1점 획득한건 아니지만 3점이니 시간이 많이 소용된듯하거나 알고리즘이 뭔가 부족한듯 합니다. 그래서 코드 첨삭을 받아봅니다

 

코드 첨삭

class Solution {
     fun solution(s: String): IntArray {
        val n = s.length
        val answer = IntArray(n) { -1 }
        val lastIndex = mutableMapOf<Char, Int>()

        for (i in 0 until n) {
            val ch = s[i]
            if (lastIndex.containsKey(ch)) {
                answer[i] = i - lastIndex[ch]!!
            }
            lastIndex[ch] = i
        }

        return answer
    }
}

 

기본적으로 Array 를 사용하는것과 List 를 사용하는것과에서 속도 차이가 확 드러나는것을 알게 되었습니다. 제가 위에 작성한 코드에 List 대신 Array 만 바뀌어도 코드 첨삭과 흡사한 결과가 나왔습니다.

 

List -> Array 변환 코드

class Solution {
    fun solution(s: String): IntArray {
        val n = s.length
        val answer = IntArray(n) { -1 }
        val map = mutableMapOf<Char, Int>()
        
        for (i in 0 until n) {
            if (map.containsKey(key = s[i])) {
                answer[i] = i - map.get(key = s[i])!!
            } else {
                answer[i] = -1
            }
            map.put(s[i], i)
        }
    
        return answer
    }
}

 

다른 사람 코드

class Solution {
    fun solution(s: String): List<Int> {
        return s.withIndex().map { (i, c) -> s.slice(0 until i).lastIndexOf(c).let { if (it >= 0) i - it else -1 } }
    }
}

 

내장 함수를 사용해서 함수들을 체이닝해서 만드는건 좋은것 같으나 속도적인 부분에서는 효율적이지 못한 부분이 어쩔 수가 없다는것을 느낍니다.